除了Fisher-Yates和找到「下一個排列？」還有什麼混洗算法？

Question

具體在相同類型的一維項目集的領域，如整數向量。

例如，假設您有一個大小爲32,768的矢量，其中包含從0到32,767的已排序整數。

我的意思是「下一個排列」是在詞彙排序系統中執行下一個排列。

維基百科lists two，如果有，我想知道更多的（除了一些BOGO：P）

Answer 1

O（N）執行 這是基於Eyal Schneider的映射Zn！ - > P（n）

def get_permutation(k, lst): 
    N = len(lst) 
    while N: 
     next_item = k/f(N-1) 
     lst[N-1], lst[next_item] = lst[next_item], lst[N-1] 
     k = k - next_item*f(N-1) 
     N = N-1 
    return lst 

它通過整合轉換步驟和查找排列來減少他的O（N^2）算法。它基本上與Fisher-Yates具有相同的形式，但是隨着映射的下一步將呼叫替換爲隨機。如果映射實際上是一個雙射（我正在努力證明），那麼這是一個比Fisher-Yates更好的算法，因爲它只調用一次僞隨機數生成器，因此效率更高。還要注意，這返回置換（N！ - k）的行爲而不是置換k，但是這不重要，因爲如果k在[0，N！]上是均勻的，那麼N也是！ - k。

老答案

這是稍微涉及到「下一個」置換的想法。如果項目可以很好地排序，那麼可以在排列上構建字典排序。這允許您從整數構造一個映射到排列空間。

然後找到一個隨機排列等同於選擇一個0到N之間的隨機整數！並構造相應的排列。該算法與計算所討論的集合的第n個排列一樣有效（並且難以實現）。如果我們對n的選擇是一致的，那麼這簡單地給出了統一的排列選擇。

有關訂購排列的更多細節。給定一組S = {a b c d}，數學家將S作爲一組排列組合來查看組合。如果p是一個置換，可以說(b a c d)，則p通過將b設置爲a，a到c，c到d和d到b來操作S。如果q是另一個置換，則可以說(d b c a)然後pq通過首先應用q然後p得到(d a b)(c)。例如，q將d帶到b，p帶b到a，使得pq帶d到a。你會看到pq有兩個週期，因爲它需要b到d並修復c。通常省略1個週期，但爲了清楚起見，我將其留下。

我們將使用一些來自羣論的事實。

1. 不相交週期通勤。 (a b)(c d)與(c d)(a b)相同
2. 我們可以按任意循環順序排列循環中的元素。即(a b c) = (b c a) = (c a b)

因此，給定一個置換，排序循環，使最大的循環先來。當兩個週期長度相同時，排列它們的項目，使得最大的項目（我們總是可以訂購一個可數的集合，即使任意這樣）項目也是第一個。然後，我們首先對循環的長度進行辭典排序，然後對其內容進行排序。這是有序的，因爲包含相同週期的兩個置換必須是相同的置換，所以如果p > q和q > p然後p = q。

該算法可以在O（N！logN！+ N！）時間中簡單地執行。只是構建所有的排列（編輯：只是要清楚，當我提出這個問題時我有數學家的帽子，反正它是舌頭），快速排列並找到第n個排列。這是一個不同於你提到的兩個算法。

Answer 2

另一種可能性是建立一個LFSR或PRNG以期爲要項目數。

Answer 3

從排序的數組開始。選擇2個隨機索引，切換這些索引處的元素。重複O（n lg n）次。

您需要重複O（n lg n）次以確保分佈接近一致。 （您需要確保每個索引至少被挑選一次，這是一個球中問題。）

Answer 4

您可以調整合並排序，使其隨機隨機混洗而不是排序它。

特別是，在合併兩個列表時，您可以隨機選擇新的頭元素，而不是選擇它作爲最小的頭元素。從第一個列表中選擇元素的概率必須是n/(n+m)，其中n是第一個列表的長度，第二個列表的長度是m。

我在這裏寫了一個詳細的解釋：Random Permutations and Sorting。

Answer 5

這裏是一個想法如何改善aaronasterling的答案。它避免了生成所有N！按照它們的字典順序進行排列和排序，因此具有更好的時間複雜度。

它在內部使用非同尋常的置換表示，它模擬從收縮數組中刪除過程的選擇。例如，序列< 0,1,0>表示從[0,1,2]中刪除項目＃0，然後從項目[1,2]中刪除項目＃1，然後從項目＃0中刪除項目＃ 1]。由此產生的排列是< 0,2,1>。用這種表示法，第一個置換總是< 0,0，... 0>，最後一個總是< N-1，N-2，... 0>。我將稱這種特殊表示爲「數組表示法」。

顯然，大小爲N的數組表示可以在O（N^2）時間內轉換爲標準置換表示，方法是使用數組並在必要時收縮它。

下面的函數可用於返回第K置換{0,1,2 ...，N-1}，在數組表示：

getPermutation(k, N) { 
    while(N > 0) { 
     nextItem = floor(k/(N-1)!) 
     output nextItem 
     k = k - nextItem * (N-1)! 
     N = N - 1 
    } 
} 

該算法工作在O（N^2）時間（由於表示轉換），而不是O（N！log N）時間。

--Example--

getPermutation（4,3）返回< 2,0,0>。此數組表示對應於< C，A，B>，這是真正的指數4排列在{A，B，C}的有序列表排列：

ABC 
ACB 
BAC 
BCA 
CAB 
CBA