排列查找算法的分析（僞代碼）

Question

A SO post關於生成所有的排列讓我想到了一些替代方法。我正在考慮使用空間/運行時的折衷方案，並想知道人們是否可以在嘗試使用C＃實現時批評這種方法和可能的打嗝。

的步驟去如下：

1. 鑑於均勻元素的數據結構，在計數結構元件的數目。

2. 假設置換包括該結構的所有的元素，從步驟1

3. 計算值的階乘實例化<key(Somehashofcollection),Collection<data-structure of homogeneous elements>>類型的一個較新的結構（詞典）和初始化的計數器。

4. 散列（???）來自步驟1的種子結構，並將散列和集合的鍵/值對插入字典中。通過1

5. 隨機遞增計數器洗牌（???）種子結構的順序，它散列，然後嘗試將其插入字典從步驟3

6. 如果存在衝突在哈希中，再次重複步驟5以獲得新的訂單和散列並檢查衝突。一旦成功插入由1

7. 直到計數器等於步驟計算階乘重複步驟5 & 6，計數器增加2

好像做使用某種隨機的這種方式（這對我來說目前是一個黑匣子）可能有助於在不合理大小的數據集的適當時間範圍內獲取所有的排列組合。

這將是巨大的，得到這麼偉大的思想家一些反饋，進一步分析這種做法，其目的是從傳統的蠻力方法在這種性質的算法普遍，也實現這樣的算法的反響偏離使用C＃。

感謝

Answer 1

與標準的已知方法相比，這種生成所有置換的方法並不好。

假設你有n件物品和M = n！排列。

代的這種方法有望發現之前產生M * LNM排列所有M.

（看到這個答案有可能解釋：Programing Pearls - Random Select algorithm）

此外，將散列函數是什麼呢？對於一個合理的散列函數，我們可能不得不很快處理非常大的整數問題（當然，任何n> 50）都不要記住確切的截點。

這種方法也消耗了很多內存（所有排列的散列表）。即使假設哈希值是完美的，這種方法將採用預期的歐米茄（Omega）操作和保證的歐米茄（nM）空間，而標準的公知方法可以在O（M）時間和O （n）空間。

作爲一個起點，我建議你可以閱讀：Systematic Generation of All Permutations這相信是O（nM）時間和O（n）空間，並且仍然比這個方法好得多。

請注意，如果必須生成所有排列，則任何算法都必須採用歐米茄（M）步驟，因此上面提到的方法是最優的！

Answer 2

這似乎是一個複雜的方式來隨機化產生的排列順序。就時間效率而言，你無法比「蠻力」方法做得更好。