排列查找算法的分析（伪代码）

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

这似乎是一个复杂的方式来随机化产生的排列顺序。就时间效率而言，你无法比“蛮力”方法做得更好。