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

Question

假设我有一个整数数组int a[] = {0, 1, ... N-1},其中N是的大小a.现在,我需要生成的所有排列as表示a[i] != i所有0 <= i < N.你会怎么做？

Answer 1

这里有一些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紊乱测试,只扫描改变的元素); 这留给了读者一个练习.

Answer 2

如果您可以访问C++ STL,请使用next_permutation,并在do-while循环中对[i]!= i进行额外检查.

Answer 3

如果您想避免其他人建议的过滤方法(按字典顺序生成排列并跳过具有固定点的排列),那么您应该根据循环符号而不是单行符号(符号的讨论)生成它们.

置换的循环类型n是一个分区n,即一个弱整数的正整数序列n.置换没有固定点的条件等同于没有1s的循环类型.例如,如果n=5,那么可能的循环类型是

5
4,1
3,2
3,1,1
2,2,1
2,1,1,1
1,1,1,1,1

其中,只有5并且3,2对此问题有效,因为所有其他包含a 1.因此,策略是至少生成具有最小部分的分区2,然后对于每个这样的分区,生成具有该循环类型的所有排列.