代码

#include <cstdio>
#include <algorithm>

int pre[12], nxt[12]; bool r[11];

// neighbor_swap: 209.837 ms / ? ms
void neighbor_swap(const int size)
{
    int tot = 1, i, j, k;
    for (i = 0; i < size; i++) r[i] = false, tot *= i+1;
    for (i = 1; i < size; i++) pre[i] = i-1; pre[0] = size; nxt[size] = 0;
    for (i = 0; i < size-1; i++) nxt[i] = i+1; nxt[size-1] = size; pre[size] = size-1;
    i = 0; while (pre[i] != size) i++; while (nxt[i] != size) printf("%d ", i+1), i = nxt[i]; printf("%d\n", i+1);
    while (--tot)
    {
        i = size-1;
        while ((!r[i] && pre[i] > i) || (r[i] && nxt[i] > i)) {
            r[i--] ^= 1;
        }
        if (!r[i]) {
            j = pre[i];
            pre[i] = pre[j];
            pre[j] = nxt[pre[i]] = i;
            nxt[j] = nxt[i];
            nxt[i] = pre[nxt[j]] = j;
        } else {
            j = nxt[i];
            nxt[i] = nxt[j];
            nxt[j] = pre[nxt[i]] = i;
            pre[j] = pre[i];
            pre[i] = nxt[pre[j]] = j;
        }
        i = 0; while (pre[i] != size) i++; while (nxt[i] != size) printf("%d ", i+1), i = nxt[i]; printf("%d\n", i+1);
    }
}

int main()
{
    // neighbor_swap(5);
    neighbor_swap(9);
    // neighbor_swap(11);
    return 0;
}

评测结果