洗牌陣列的最佳算法

我有一個數組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的足夠隨機排列。

2014-10-05 read Read

這是什麼語言？爲什麼你不能只洗牌你的原始數組，而不是創建另外兩個數組，洗牌，然後用它來洗牌呢？ – 2014-10-05 03:39:47

什麼是s，A和B的關係。你的問題似乎告訴了幾個問題的不足部分。 – 2014-10-05 03:40:31

s是一個非常大的字符串序列。每個字符串大約是8000字節。 A和B是序列的排列{1,2,3，... length（s）} – 2014-10-05 03:42:37

要使用費舍爾 - 耶茨（高德納）與索引陣列中洗牌，初始化一個索引陣列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};

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

2014-10-05 04:09:59

我認爲你的代碼工作得很好。但我很好奇我的算法是否會生成一致的隨機排列。我希望有人可以給出數學證明。 – 2014-10-05 04:15:35

@readRead它不起作用;當n = 2時，在最終會計中沒有任何東西被移動。 – 2014-10-05 04:26:56

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

2014-10-05 03:41:23 MBo

Knut的shuffle比我的算法產生更多的隨機排列嗎？我使用索引數組是因爲我想以完全相同的方式對另一個數組x進行排列。 s和x有一對一的對應關係。 – 2014-10-05 03:50:00

它只是產生均勻分佈（所有的排列有相等的概率） – MBo 2014-10-05 04:30:17

回答