Permutations
異なる整数のリスト nums が与えられます。それらの値を並べ替えたすべての順序を返してください。それぞれのリストでは各値をちょうど1回ずつ使用するため、n 個の値から n! 通りの順序ができます。辞書順に並べてください。2つの順序を位置ごとに比較し、最初に異なる位置の値で順序を決めます。[1, 2, 3] の場合、[1, 2, 3] が最初になり、[3, 2, 1] が最後になります。
関数
- numsinteger-array
- 値はすべて異なり、順序は問いません
- 戻り値integer-2d-array
- 値のすべての順序を辞書順に列挙したもの
制約
1 ≤ nums.length ≤ 6-10 ≤ nums[i] ≤ 10- すべての
numsの値は異なります。 numsはどのような順序でも構いません。
例
- 入力
- nums = [3, 1, 2]
- 出力
- [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
- 説明
- 3つの値には3! = 6通りの順序があります。値を並べ替えると1、2、3なので、1で始まる順序が最初に来ます。また、2番目の位置では2が3より小さいため、
[1, 2, 3]は[1, 3, 2]より前に来ます。入力の順序は関係ありません。
- 入力
- nums = [2, -1]
- 出力
- [[-1, 2], [2, -1]]
- 説明
- 2つの値は、2通りの順序で書くことができます。-1は2より小さいため、
[-1, 2]が先に来ます。
- 入力
- nums = [7]
- 出力
- [[7]]
- 説明
- 1つの値には、リスト自体という1つの順序しかありません。
提出時に隠しテスト+13件
発展問題
ある順列が与えられたとき、辞書順で次の順列を、O(n) 時間、O(1) の追加領域で、インプレースに生成できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
順序を一度に1つの位置ずつ作っていきます。最初の位置にはいくつの値を置けますか。2番目の位置にはいくつ置けますか。そして、それは合計について何を教えてくれますか。
すでに配置されている値を記録しておきます。各位置で、まだ使われていない値をすべて試し、試し終わったら再び使える状態に戻して、次の試行を同じ状態から始められるようにします。
値をソートしてから、再帰的なヘルパー関数を書きます。パスにすべての
n個の値が含まれている場合は、コピーを記録します。そうでなければ、値を小さいものから大きいものへ順にループし、使用済みのものはスキップして、1つを使用済みにして追加し、再帰呼び出しを行ってから、それを削除して未使用に戻します。未使用の最小の値から試すことで、順序はすでにソートされた状態になります。
解説
n 個の異なる値のリストには n! 通りの並び順があり、6 個の値なら 720 通りです。答えにはそれらをすべて列挙する必要があるため、処理量は少なくとも n × n! です。課題は、それぞれの並び順を一度ずつ作り、辞書順に出力することです。ソート済みの値を使ってバックトラッキングし、未使用の値のうち常に最小のものから試せば、この両方を同時に実現できます。
各空欄に入力してから、並べ替えましょう
考え方
順列を一度に1つずつ値を増やして作ります。値がないときの順列は、空のリスト1つです。順列[1, 2]に値3を加えるには、3つの隙間それぞれに挿入します。[3, 1, 2]、[1, 3, 2]、[1, 2, 3]です。持っているすべての順列についてこれを行うと、k個の値の順列がk+1個の値の順列になります。
k+1個の値のすべての順列は、ちょうど1回ずつ作られます。そこから最新の値を取り除くと、元になった順列が1つ得られ、最新の値の位置によって挿入した隙間がわかります。そのため、個数は1、2、6、24と増え、n個の値からはn!個の順列ができます。
ただし、必要な順序では生成されません。[1, 2, 3]では、最初に作られる順列は[3, 2, 1]なので、最後に位置ごとに比較するソートが必要になります。このソートがコストのかかる部分です。n!個の順列にはおよそn! × log(n!)回の比較が必要で、そのたびに最大n個の値を読み取ります。値が6個の場合、およそ720 × 9.5 × 6、つまり約41,000回の読み取りになります。また、この方法では次の世代を作る間、1世代分の順列すべてをメモリに保持します。
アルゴリズム
- 空の順列を1つ含むリストから始めます。
numsの各値について、新しいリストを作成します。これまでの各順列と、0からその長さまでの各挿入位置について、その位置に値を挿入した順列をコピーします。- 古いリストを新しいリストに置き換えます。
- 順列を位置ごとに並べ替えて返します。
def permute(nums):
perms = [[]]
for value in nums:
grown = []
for perm in perms:
# Put value into every gap of perm, both ends included.
for gap in range(len(perm) + 1):
grown.append(perm[:gap] + [value] + perm[gap:])
perms = grown
# Insertion order is not lexicographic, so sort at the end.
perms.sort()
return perms使用済み配列を使ったバックトラッキング
考え方
n 個のスロットを左から右へ埋めます。最初のスロットには n 個、2 番目には n-1 個の候補があり、以下同様です。これが n! の由来です。これらの選択肢を木として描きます。根は空のパスで、各辺で値を 1 つ追加し、深さ n にある各葉が完成した順列です。値が 1、2、3 の場合、根の子は [1]、[2]、[3] です。[1] の子は [1, 2] と [1, 3] で、それらはそれぞれ 1 つの葉を持ちます。
バックトラッキングでは、1 つの共有された path と、値ごとの used フラグを使ってこの木をたどります。各ノードでは値をループで調べ、使用済みのものはスキップします。使用可能な値ごとに、選択し（使用済みにして追加し）、探索し（1 段深く再帰し）、それから選択を解除します（取り除いて未使用に戻します）。選択解除の手順で、ループが始まる前とまったく同じ状態に戻るため、次の値も同じノードから試せます。長さ n のパスは葉なので、コピーを記録して戻ります。
順序は自然に正しくなります。ループでは使用可能な最小の値から試し、あるプレフィックスで始まる順列をすべてたどり終えてから、そのプレフィックスを変更します。そのため、1 で始まる順列はすべて 2 で始まる順列より前になり、その中では [1, 2, ...] が [1, 3, ...] より前になります。これが辞書順です。また、最初に nums をソートする理由でもあります。ループはインデックス順に進むため、インデックスが値の順になっている必要があります。
木には約 e × n! 個のノード（e は約 2.72）があり、各ノードで n 回のループを実行するため、時間計算量は O(n × n!) です。これは答えのサイズと同じオーダーです。出力以外では、パス、フラグ、呼び出しスタックはそれぞれ最大 n 個の要素を保持します。
アルゴリズム
- 値をソートし、
n個の false フラグを持つused配列を作成します。 explore()を記述します。pathにn個の値が格納されている場合は、そのコピーを結果に追加して返します。- それ以外の場合、値が未使用である 0 から n-1 までの各インデックス
iについて、使用済みとしてマークし、values[i]を追加し（選択）、explore()を呼び出し（探索）、その後それを削除して未使用としてマークします（選択解除）。 explore()を 1 回呼び出し、結果を返します。
def permute(nums):
values = sorted(nums)
n = len(values)
result = []
path = []
used = [False] * n
def explore():
# A full path is a leaf of the decision tree: one finished ordering.
if len(path) == n:
result.append(path[:])
return
# Smallest unused value first, so the leaves come out in lexicographic order.
for i in range(n):
if used[i]:
continue
used[i] = True
path.append(values[i]) # choose
explore() # explore
path.pop() # un-choose
used[i] = False
explore()
return result
落とし穴と境界ケース
バックトラッキングのバグは、ほとんどの場合、復元されない状態、または意図せず共有される状態が原因です。
pathのコピーではなく、pathを記録している。n!個の結果がすべて同じリストになり、探索が終わると空になります。- 選択の取り消しが半分だけになっている。値を削除しても
used[i]を設定したままにすると、その値は後続の分岐で二度と現れず、n!個より少ない順列を返します。 - 最初に
numsをソートしていない。探索ですべての順列は見つかりますが、入力の順序に従うため、入力が[3, 1, 2]なら、それが最初に列挙されます。 - 最終的なソートをせずに、交換方式（
nums[start]を後続の各位置と交換し、再帰呼び出しを行い、元に戻す）を使っている。n!個の順列はすべて見つかりますが、[1, 2, 3]の場合、[3, 1, 2]より先に[3, 2, 1]が列挙されます。 path内を検索して、値が使用済みかどうかを確認している。ここで機能するのは値が異なる場合に限られ、各ステップでnのコストがかかります。インデックスごとにフラグを使えばO(1)で、値が重複する場合でも機能します。
よくある質問4
n 個の異なる要素を持つリストには、何通りの順列がありますか？
n! は「n の階乗」と読みます。最初の位置には n 通り、2 番目には n-1 通り、最後には 1 通りの選択肢があり、それらをすべて掛け合わせます。値が3つなら並べ方は6通り、6つなら720通り、10個ではすでに3,628,800通りになります。そのため、順列の問題では n を小さく保ちます。
すべての順列を生成する時間計算量はどれくらいですか？
O(n × n!)。順列は n! 通りあり、それぞれを書き出すのに n ステップかかるため、すべてを返さなければならない場合、これより効率のよい方法はありません。バックトラッキングはこの限界に達し、出力以外に、現在の経路、使用済みフラグ、再帰のために O(n) の領域を必要とします。
バックトラッキングでは、なぜ辞書順に順列が生成されるのでしょうか？
これは、利用可能な最小の値から試していく深さ優先探索です。次の接頭辞に移る前に、ある接頭辞から始まるすべての順列を列挙し、接頭辞は小さいものから大きいものへと試します。探索を始める前に入力をソートしておけば、これは辞書の単語の並び順と一致します。
入力に重複がある場合、順列はどのように生成しますか？
値をソートし、各位置で、その前の値と等しく、かつその前のコピーが使用中でない値をスキップします。条件は i > 0、values[i] == values[i-1]、!used[i-1] です。これにより、等しい値は元の順序で配置され、それぞれ異なる並び順が一度だけ作られます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def permute(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 1, 2]
期待値
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]