试图理解Knuth的排列算法

Question

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

下面是设置：

数组是一个指针，指向持有置换的被调出的数组。它不适当地存储n个值，每个位置保存索引+ 1。

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

1，2，3，4，5，6，7，8，9，10

"rand“变量包含一些从1到n的变量(在本例中，1-10)。

交换应该是一个做一些排他性或交换(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)

然后，我们尝试异或两个参数：

第一：&阿拉伊

这是指向恶意数组的指针的地址。(双指针，对吗？)

第二个参数是完全一样的。指向恶意数组的指针的地址。

为什么我要对地址做异或呢？

我有什么不明白的？

感谢所有的帮助！

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;
}

这可能就是某个人在交换中做异或的意思。

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

给定rand( x )在0，x中返回一个数字，您需要这样的内容：

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

它的工作方式很简单:对于每个arrayi，它从尚未被选择的元素中随机选择一个元素。