如何生成 a[i] != i 的排列？

假设我有一个整数数组int a[] = {0, 1, ... N-1}, where N的大小是a。现在我需要生成所有排列a s that a[i] != i对全部0 <= i < N。你会怎么做？

下面是一些 C++ 实现的算法，该算法基于递归的双射证明

!n = (n-1) * (!(n-1) + !(n-2)),

where !n是混乱的数量n items.

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

static const int N = 12;
static int count;

template<class RAI>
void derange(RAI p, RAI a, RAI b, int n) {
    if (n < 2) {
        if (n == 0) {
            for (int i = 0; i < N; ++i) p[b[i]] = a[i];
            if (false) {
                for (int i = 0; i < N; ++i) std::cout << ' ' << p[i];
                std::cout << '\n';
            } else {
                ++count;
            }
        }
        return;
    }
    for (int i = 0; i < n - 1; ++i) {
        std::swap(a[i], a[n - 1]);
        derange(p, a, b, n - 1);
        std::swap(a[i], a[n - 1]);
        int j = b[i];
        b[i] = b[n - 2];
        b[n - 2] = b[n - 1];
        b[n - 1] = j;
        std::swap(a[i], a[n - 2]);
        derange(p, a, b, n - 2);
        std::swap(a[i], a[n - 2]);
        j = b[n - 1];
        b[n - 1] = b[n - 2];
        b[n - 2] = b[i];
        b[i] = j;
    }
}

int main() {
    std::vector<int> p(N);
    clock_t begin = clock();
    std::vector<int> a(N);
    std::vector<int> b(N);
    for (int i = 0; i < N; ++i) a[i] = b[i] = i;
    derange(p.begin(), a.begin(), b.begin(), N);
    std::cout << count << " permutations in " << clock() - begin << " clocks for derange()\n";
    count = 0;
    begin = clock();
    for (int i = 0; i < N; ++i) p[i] = i;
    while (std::next_permutation(p.begin(), p.end())) {
        for (int i = 0; i < N; ++i) {
            if (p[i] == i) goto bad;
        }
        ++count;
    bad:
        ;
    }
    std::cout << count << " permutations in " << clock() - begin << " clocks for next_permutation()\n";
}

在我的机器上，我得到

176214841 permutations in 13741305 clocks for derange()
176214841 permutations in 14106430 clocks for next_permutation()

恕我直言，这是一种洗涤。可能双方都需要做出改进（例如，重新实施next_permutation通过仅扫描发生变化的元素的混乱测试）；这留给读者作为练习。