试图理解 Knuth 的排列算法

Question

我最近在我的一个算法中得到指示类使用 Knuth 的算法来创建存储在 malloc 数组中的排列。

设置如下：

array 是指向保存排列的分配数组的指针。它最初存储 n 个值，每个位置保存索引 + 1。

因此，如果 n 为 10，则数组最初为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

"rand" 变量保存从 1 到 n 的一些变量。（在这个例子中，1-10）。

Swap 应该是一个执行位异或交换 (XOR) 的函数。

最终结果应该是 1-n 的某种排列。

所以 [5, 6, 2, 8, 7, 4, 1, 3, 10, 9] 作为一种可能的排列是有效的。

但是，[1, 1, 5, 7, 8, 2, 3, 5, 5, 6] 无效，因为它不是排列。它有重复项。

但我无法理解我们被告知要使用的这段代码：

for(i = 1; i < n; i++) {
    swap(&array[i], &a[rand]);
}

所以我们从数组的第二个元素开始。 (i = 1)

然后我们尝试对两个参数进行异或运算：

首先：&array[i]

这是指向分配数组的指针的地址。（双指针，对吧？）

和第二个参数完全一样。指向分配数组的指针的地址。

我到底应该如何以及为什么要对地址进行异或运算？

我有什么不明白的？

感谢所有帮助！

Answer 1

首先，交换不应该做按位异或。它应该交换。

通常是这样写的：

void swap(int *a, int *b)
{
    int t=*a;
    *a=*b;
    *b=t;
}

但是有一个使用 XOR 的技巧不需要额外的变量。您可以像这样实现交换：

void swap(int *a, int *b)
{
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

这可能是某人在交换中执行 XOR 的意思。

其次，rand 的范围必须从 0 到 i，而不是 1 到 n，如果您想要一个无偏随机排列。

给定 rand(x) returns [0,x] 中的一个数字，你想要这样的东西：

for (int i=n-1; i>0; --i)
{
    j = rand(i);
    if (i!=j)
    {
        swap(&array[i],&array[j]);
    }
}

它的工作方式很简单：对于每个数组[i]，它从尚未选取的元素中随机选择一个元素。

Trying to understand Knuth's algorithm for permutations