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

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

这是一些C ++实现基于递归的双射证明的算法

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

项目

!n

的排列数量在哪里

n

。

#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

排列仅扫描已更改元素的重排测试）；留给读者练习。