1

Given an array of intergers, write a program to print all the permutations of the numbers in the array. The output should be sorted in a non-increasing order.

For example for the array {12, 4, 66, 8, 9}, the output should be:

9866412
9866124
9846612
....
....
1246689

I thought of generating all permutations at the same time inserting them in a BST, then performing reverse inorder on BST. This seems highly inefficient, as I'm storing the permutations, can we do better ?

4

4 回答 4

0

首先使用数字对数字进行排序（也许将它们转换为字符串）。例如，9 大于 11。您可以为此实现一个简单的插入排序。
所以现在你有一个以这种方式排序的数字列表（比如说 n1、n2、n3、n4）。
使用此列表，您可以轻松获得所有已排序的排列，合并列表中的元素并在生成过程中交换最后一个。
即：n1n2n3n4、n1n2n4n3、n1n3n2n4……等等。

例子 ：
4,11,76,100 100,11,4,76
10011476,10011764,10041176
...

k*n^2k数字的最长大小（示例中为 3，由数字 100 给出），因为如果有相似的数字，您需要比较它们的所有数字（如 10000 和 100001）。然后你只需要生成所有排列，这需要n!. 最终的时间复杂度是O(n!)，不需要额外的空间。

于 2013-01-20T16:04:30.707 回答
0

c++ STL：

vector arr = .. sort(arr.begin(),arr.end())
do
{
// 在这里处理你的数据
}while(next_permutation(arr.begin(),arr.end());

这在 O(2^n) 中为你做你想做的事。在内部，它通过有效的方式交换来实现。如果您需要进一步的帮助，请告诉我

于 2013-01-20T15:43:15.377 回答
0

如果您使用的是 Python，模块 itertools 有一个解决方案，请参见此处。

如果您可以访问 Knuth 的The Art of Computer Programming第 4 卷，第 2 册，它有许多解决方案，包括递归和迭代。

此外，RosettaCode 有多种语言的解决方案，请参见此处。Fortran 77 解决方案是迭代的，您可以对其进行调整以满足您的需求，或将其翻译成任何语言。它以字典升序给出解决方案。

现在，如果我不明白您的要求，您需要按降序排列的解决方案，考虑连接数字字符串的顺序。可能很难直接实现，因为例如（100,99,999）谁“小于”（99,100,999），这将小于（999,99,100）：“10099999”<“99100999”<“99999100”。您不能简单地使用数字列表的字典顺序。但是，很容易按字典顺序生成排列。

于 2013-01-20T18:51:16.633 回答
0

出于推理，我会递归地这样做：

  • 如果数组的长度为 1，则输出一个排列（数组本身）
  • 如果有两个或更多元素，则一次选择一个元素（首先选择最大的元素，然后再选择较小的元素，直到找到最小的元素）。对于选择的每个元素a，您执行以下操作：
    • a从数组中取出，得到一个比原数组少一个元素的数组。递归生成这个新获得的数组的所有排列，并在每个递归生成的排列a前面添加。

这种方法基本上对应于您将排列存储在搜索树（但是，不是二进制树）中并枚举它们的想法。尽管如此，它还是使用递归堆栈来执行此操作，并且不存储整个树。

另一种方法可能使用阶乘数字系统。这可用于正确枚举排列。因此，您可以“仅倒数并重建相应的排列”。

于 2013-01-20T19:02:47.843 回答