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

Question

假设我有一个整数数组 int a[] = {0, 1, ... N-1}，其中 N 是 a< 的大小/代码>。现在我需要为所有 0 <= i 生成 a 的所有排列 a[i] != 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，并对[i] != i 在 do-while 循环中。

Answer 3

如果您想避免其他人建议的过滤方法（按字典顺序生成排列并跳过具有固定点的排列），那么您应该基于循环符号而不是单行符号（符号讨论）。

n 排列的循环类型是 n 的划分，即总和为 n 的正整数的弱递减序列。排列没有不动点的条件等价于其循环类型没有1。例如，如果 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 对于此问题有效因为所有其他都包含 1。因此，策略是生成最小部分至少为 2 的分区，然后对于每个这样的分区，生成具有该循环类型的所有排列。

Answer 4

您正在寻找的排列称为混乱。正如其他人所观察到的，均匀随机分布的排列可以通过生成均匀随机分布的排列然后拒绝具有固定点（其中 a[i] == i）的排列来生成。拒绝方法在时间 e*n + o(n) 中运行，其中 e 是欧拉常数 2.71828... 。与 @Per 类似的替代算法的运行时间为 2*n + O(log^2 n)。然而，我能找到的最快算法，即早期拒绝算法，运行时间为 (e-1)*(n-1)。不是等待排列生成然后拒绝（或不拒绝）排列，而是在构造排列时测试固定点，从而可以尽早拒绝。这是我在 Java 中实现的早期拒绝混乱方法。

  public static int[] randomDerangement(int n)
    throws IllegalArgumentException {

    if (n<2)
      throw new IllegalArgumentException("argument must be >= 2 but was " + n);

    int[] result = new int[n];
    boolean found = false;

    while (!found) {
      for (int i=0; i<n; i++) result[i] = i;
      boolean fixed = false;
      for (int i=n-1; i>=0; i--) {
        int j = rand.nextInt(i+1);
        if (i == result[j]) {
          fixed = true;
          break;
        }
        else {
          int temp = result[i];
          result[i] = result[j];
          result[j] = temp;
        }
     }
      if (!fixed) found = true;
    }

    return result;
  }

有关替代方法，请参阅我的帖子 随机播放列表，确保没有任何项目保持在同一位置。

Answer 5

只是一个预感：我认为词典排列可能可以通过修改来解决这个问题。

通过将奇数和偶数元素对交换为 2,1,4,3,6,5 来重新排列数组 1,2,3,4,5,6,... ,... 以最低字典顺序构造排列。然后使用标准算法，并附加一个约束，即您不能将元素 i 交换到位置 i。

如果数组有奇数个元素，则必须在末尾再次进行交换，以确保元素 N-1 不在位置 N-1 中。

Answer 6

这是 python 中的一个小型递归方法：

def perm(array,permutation = [], i = 1):
    if len(array) > 0 :
        for element in array:
            if element != i:
                newarray = list(array)
                newarray.remove(element)

                newpermutation = list(permutation)
                newpermutation.append(element)

                perm(newarray,newpermutation,i+1)
    else:
        print permutation

运行 perm(range(1,5)) 将给出以下输出：

[2, 1, 4, 3]
[2, 3, 4, 1]
[2, 4, 1, 3]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 3, 1, 2]
[4, 3, 2, 1]