再帰的および非再帰的アルゴリズムを使用して配列のすべての順列を生成するにはどうすればよいですか?

配列の順列: 詳細な説明

配列の順列を生成するには、要素がどのように配置されているかを理解することが重要です。順列には、配列要素を再配置して新しいシーケンスを作成することが含まれます。 n 個の要素を持つ配列で可能な順列の数は、n! で与えられます。

再帰アルゴリズム

順列を生成する 1 つの方法は、再帰的アプローチを使用することです。要素を繰り返し交換し、残りの配列に順列を適用します。 elements.

このアルゴリズムは、最初の要素を残りの各要素と交換することから始まります。次に、同じ操作を残りの要素に再帰的に適用します。各再帰呼び出しの後、要素は元の位置に戻されます。

非再帰アルゴリズム

反復アプローチの場合は、次の手順を検討してください。

1. 昇順にソートされた配列から開始しますorder.
2. シーケンスが降順にならない最初のインデックスを検索します (つまり、a[i]
3. 値が次の値に達する最後のインデックスを検索します。 a[i-1] 以上です。
4. a[i-1] を最後の要素と入れ替えますIndex.
5. 配列の末尾の要素の順序を反転します (インデックス i-1 の後)。

例: 配列の並べ替え [3, 4, 6] 、2、1]

再帰的アルゴリズム:

1. 3 と 4 を交換: [4, 3, 6, 2, 1]
2. 再帰的に並べ替え [4, 3, 6, 2, 1]
3. 3 と 6 を交換します: [4, 6, 3, 2, 1]
4. 再帰的に並べ替え [4, 6, 3, 2, 1]
5. すべての並べ替えが生成されるまで続行

非再帰アルゴリズム:

1. [1, 2, 3, 4, 6] から開始 (昇順にソート)
2. 順序は降順なので、ステップ 3 に進みます
3. a[i] < となる最初のインデックスを検索します。 a[i-1]: 3
4. a[j] >= a[i-1] である最後のインデックスを見つけます: j = 5、6 >= 3
5. a[i-1] を次のものと交換します。 a[j]: [1, 2, 6, 3, 4, 5]
6. 配列の末尾を反転します。 [1, 2, 3, 4, 5, 6]
7. 配列が降順になるまで手順 3 ～ 6 を繰り返します (すべての置換が生成されたことを示します)

結果どちらのアルゴリズムも同じです。すべての可能な順列が生成され、出力されます。

以上が再帰的および非再帰的アルゴリズムを使用して配列のすべての順列を生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。