洗牌陣列的最佳算法

Question

我有一個數組s = {'ACA'，'BBC'，'CKA'，...};

我想洗牌s。所以我創建列表A = {1,2,3,4 ..}和列表B = {1,2,3,4，...}

然後，我洗牌兩個列表。 random.shuffle（A） random.shuffle（B）

最後，我交換S [A [0]]其中s [B [0]]，交換S [A [1]]其中s [B [1]] .....

該算法是否會產生s的隨機排列？它足夠隨機？假設random.shuffle產生A和B的足夠隨機排列。

Answer 1

要使用費舍爾 - 耶茨（高德納）與索引陣列中洗牌，初始化一個索引陣列A像

for (int i = 0; i < n; i++) A[i] = /* random integer in 0..i */; 

，然後做掉一樣

for (int i = 0; i < n; i++) swap(&s[A[i]], &s[i]); 

你的算法不生成均勻的隨機排列。當n = 2時，A和B的可能性爲

A = {0, 1}; B = {0, 1}; 
A = {0, 1}; B = {1, 0}; 
A = {1, 0}; B = {0, 1}; 
A = {1, 0}; B = {1, 0}; 

這些都對起始置換沒有任何影響;要麼兩個元素都與自己交換，要麼重複兩次相同的非平凡交換，取消其效果。

Answer 2

Knut's shuffle是簡單且有效的方法來混洗數組。你不需要額外的索引數組。他們使用有什麼特別的理由嗎？