算法重新排列的數組

Question

我有一個數組：

1 1A 2 2A 3 3A 4 4A 5 5A 

我需要通過隨機重新安排它，條件：1A必須背後1，圖2A落後2 ...（不一定喜歡1 1A ）

的期待後導致重新排列如下：

1 4 2 4A 3 2A 5 1A 5A 3A 

幫助我的最好的算法（最好的速度）

Answer 1

你可以嘗試這樣的：

• 組的元素融入到不同的隊列，使得所有具有某種「秩序」的元素在同一個隊列，例如[[1, 1A], [2, 2A, 2B], [3, 3A], ...]
隨機
• 選擇那些隊列之一，移除第一元件並將其添加到你的結果
• 重複，直到所有隊列爲空

萬一部分排序是更復雜的，例如如果某些元素a必須在b和c之前，但在b和c之間沒有偏序，則可以對樹或類似元素執行相同操作。

此外，正如@vib所指出的，爲了確保結果中元素的均勻分佈，您應該選擇與隊列中剩餘元素的數量成比例的不同隊列。

Answer 2

• 隨機陣列（Fisher yates shuffle）
• 對於每個x，xA對 - 如果x在xA之後，則切換它們。這可以通過在O(n)中爲陣列中的所有元素創建map:Element->Index來完成。

總複雜性：O(n)（時間）平均情況
輸出被保證是隨機均勻地混洗，從Fisher-耶茨的正確性。

僞代碼：

array = shuffle(array) 
map = new map 
for each element e in array with index i: 
    map.add(e,i) 
for each element e in the array: 
    if e is "x" (not "xA"): 
     i = map.get(e) 
     j = map.get(xA) 
     if j<i: 
     swap(arr,i,j) 

• 如果有比只有2（X，XA，XB，...）更多的 - 你可以列出所有這些，排序在主迴路，在類似的方式。