\(P\) に対して操作を何回か行って順列 \(Q\) が得られた場合を考えます。

この時、\(\{P_0,P_1,\ldots,P_{2^{N-1}-1}\}=\{Q_0,Q_1,Q_2,\ldots,Q_{2^{N-1}-1}\}\) または \(\{P_0,P_1,\ldots,P_{2^{N-1}-1}\}=\{Q_{2^{N-1}},Q_{2^{N-1}+1},\ldots,Q_{2^N-1}\}\) が成り立ちます。これは\((a,b)=(0,N)\) 以外の操作では \(P_0,P_1,\ldots,P_{2^{N-1}-1}\) と \(P_{2^{N-1}},P_{2^{N-1}+1},\ldots,P_{2^N-1}\) の間で入れ替わる要素が存在しないこと、\((a,b)=(0,N)\) の操作を行っても互いに完全に入れ替わることから言えます。また、得られるすべての順列 \(Q\) について、\((a,b)=(0,N)\) の操作を最後の操作以外では行わないで得ることができます。

\((a,b)=(0,N)\) の操作を行わず、 \((P_0,P_1,\ldots,P_{2^{N-1}-1})\) に対して操作を行うことで得られる辞書順最小の数列を \(A\) 、\((P_{2^{N-1}},P_{2^{N-1}+1},\ldots,P_{2^N-1})\) に対して操作を行うことで得られる最小の数列を \(B\) とします。

\(A_0<B_0\) のとき

\((a,b)=(0,N)\) の操作を行わないで \(A\) と \(B\) をこの順でつなげたものが得られる辞書順最小の数列です。

\(A_0>B_0\) のとき

\((a,b)=(0,N-1),(1,N-1)\) の操作を行ったあと、\((a,b)=(0,N)\) の操作を行うことで \(B\) と \(A\) をこの順でつなげた数列が得られます。また、これが得られる辞書順最小の数列になります。

つまり、数列の大きさが半分にした問題を \(2\) 回解き、その結果から元の数列から得られる辞書順最小の数列が求められます。また、大きさが \(1\) の数列は当然操作を行わなくてよいです。 よって、再帰的にこの問題を解くことができます。時間計算量は \(\mathrm{O}(N 2^N)\) になります。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    for (int test = 0; test < t; ++test) {
        int n;
        cin >> n;
        vector<int> p(1 << n);
        for (auto& e : p)
            cin >> e;
        auto solve = [&](auto&& solve, int l, int r) -> vector<int> {
            if (r - l == 1) return {p[l]};
            int mid = (l + r) / 2;
            vector<int> a = solve(solve, l, mid);
            vector<int> b = solve(solve, mid, r);
            if (a[0] > b[0]) swap(a, b);
            a.insert(a.end(), b.begin(), b.end());
            return a;
        };
        vector<int> ans = solve(solve, 0, 1 << n);
        for (int i = 0; i < (1 << n); ++i) {
            cout << ans[i] << " \n"[i == (1 << n) - 1];
        }
    }
}