試圖瞭解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]，它選擇一個元素隨機從尚未被挑選的那些。