配列のすべての順列を生成するにはどうすればよいですか?

配列の順列の生成

配列の順列は、その要素の一意の配置で構成されます。 N 要素の配列の場合、N! が存在します。 (N 階乗) の個別の順列。この質問は、これらの順列を生成するアルゴリズムの概要を説明することを目的としています。

アルゴリズム:

配列の順列を生成するための次の手順を検討してください:

1. 初期化: 最初の要素をピボットとして取得し、配置することから始めます。現在の順列リストの最初の位置にあります。

2. 再帰的順列: 配列の残りの要素をループします。各要素をピボットと交換し、次の位置で更新されたピボットを使用して置換関数を再帰的に呼び出し、再度交換して元の順序を復元します。

   • たとえば、{3,4,6, 2,1} をピボット 3 に設定すると、{4,6,2,1} を繰り返します。 4 を 3 と交換し、ピボット 4 で {4, 3, 2, 1} を再帰的に並べ替えて、元に戻します。
3. 終了: ループが最後の要素で、現在の順列リストが完成します。それを出力します。

実装:

上記のアルゴリズムの Python 実装は次のとおりです:

def generate_permutations(arr):
  perms = []
  _generate_permutations_helper(arr, 0, perms)
  return perms


def _generate_permutations_helper(arr, start, perms):
  if start == len(arr) - 1:
    perms.append(arr.copy())
  else:
    for i in range(start, len(arr)):
      arr[start], arr[i] = arr[i], arr[start]
      _generate_permutations_helper(arr, start + 1, perms)
      arr[start], arr[i] = arr[i], arr[start]

例使用法:

arr = [3, 4, 6, 2, 1]
permutations = generate_permutations(arr)
print(permutations)  # [[3, 4, 6, 2, 1], [3, 4, 2, 6, 1], ... ]

注: このメソッドは、現在の順列の開始要素と終了要素のみを維持し、完全なリストを最初の時点でのみ構築することで、メモリ使用量を最適化できます。これにより、順列のリスト全体をメモリ内に保持する必要がなくなります。

以上が配列のすべての順列を生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。