试图了解Knuth的排列算法

Question

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

这里是设置：

阵列是一个指向一个malloced阵列保持置换。据intially存储的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）

然后我们试图异或2个paramenters：

第一：&阵列[I]

即一个指针malloced数组的地址。 （双指针，对吧？）

而第二个参数是完全一样的东西。指向malloced数组的指针的地址。

如何以及为什么我应该在地址上进行异或操作？

我不理解什么？

感谢任何及所有的帮助！

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，你需要一个无偏的随机排列组合。

鉴于兰特（x）将返回一个数字[0，X]，你想是这样的：

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

它的工作方式很简单：为每个阵列[I]，它选择一个元素随机从尚未被挑选的那些。