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

推論のために、私はそれを再帰的に行います：

  • 配列の長さが1の場合、単一の順列を1つ出力します（配列自体）
  • 2つ以上の要素がある場合は、一度に1つの要素を選択します（最初に最大の要素を選択し、最小の要素に到達するまで小さい要素に進みます）。選択した要素ごとaに、次の手順を実行します。
    • 配列から削除aし、元の配列より1つ少ない要素を含む配列を取得します。この新しく取得された配列のすべての順列を再帰的に生成し、再帰的に生成された各a順列の前に追加します。

このアプローチは、基本的に、順列を検索ツリー（ただし、バイナリツリーではない）に格納し、それらを列挙するというアイデアに対応しています。それでも、再帰スタックを使用してこれを行い、ツリー全体を格納するわけではありません。

別のアプローチでは、階乗数法を使用する場合があります。これは、順列を適切に列挙するために使用できます。したがって、「逆算して、対応する順列を再構築する」ことができます。

于 2013-01-20T19:02:47.843 に答える
0

Python を使用している場合は、モジュール itertools に解決策があります。こちらを参照してください。

Knuth のThe Art of Computer Programming volume 4, fascicule 2 にアクセスできる場合は、再帰的および反復的な多くのソリューションがあります。

また、RosettaCode には多くの言語のソリューションがあります。こちらを参照してください。Fortran 77 ソリューションは反復的であり、ニーズを満たすように適応させたり、任意の言語に翻訳したりできます。辞書式の昇順でソリューションを提供します。

さて、あなたが何を求めているのかわからない場合は、連結された数字の文字列の順序を考慮して、降順で解決策が必要です。たとえば、(100,99,999) が (99,100,999) よりも「小さい」場合、(999,99,100) よりも小さい ("10099999" < "99100999" < "99999100") ため、直接実装するのは難しい場合があります。数字のリストの辞書式順序を単純に使用することはできません。ただし、辞書順で順列を生成するのは非常に簡単です。

于 2013-01-20T18:51:16.633 に答える
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

最初に数字を使用して数字を並べ替えます (おそらく文字列に変換します)。たとえば、9 は 11 より大きいです。これには、単純な挿入ソートを実装できます。
これで、このようにソートされた数値のリストができました (n1、n2、n3、n4 としましょう)。
このリストを使用すると、すでにソートされているすべての順列を簡単に取得し、リスト内の要素をマージし、生成が進むにつれて最後の要素を交換できます。
つまり、n1n2n3n4、n1n2n4n3、n1n3n2n4... などです。

例:
4, 11, 76, 100
100, 11, 4, 76
10011476, 10011764,

10041176 k*n^2...k数値の最長サイズ (例では 3、数値 100 で指定)。同様の数値がある場合は、すべての桁を比較する必要があるため (10000 と 100001 など)。次に、すべての順列を生成するだけで済み、これにはn!. 最終的な複雑さはO(n!)なく、余分なスペースは必要ありません。

于 2013-01-20T16:04:30.707 に答える