这是一些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排列仅扫描已更改元素的重排测试）；留给读者练习。