我最近在我的一个算法类中被指示使用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）
然后，我们尝试对两个参数进行 XOR 运算：
第一个：&数组[i]
这是指向错误定位数组的指针的地址。（双指针，对吧？
第二个参数是完全相同的。指向错误定位数组的指针的地址。
我到底应该如何以及为什么应该对地址进行异或？
我不明白什么？
感谢您的任何帮助！
首先，swap 不应该做按位独占 or。 它应该交换。
通常，这是写的：
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;
}
这可能就是某人在交换中进行异或的意思。
其次，兰德的范围必须从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]);
}
}
它的工作方式很简单：对于每个数组[i]，它从尚未选择的元素中随机选择一个元素。