13.6 演習¶
13.6.1 確認問題¶
1. この順列アルゴリズムは結果を取りこぼすか¶
あるバックトラッキングアルゴリズムは、1、2、3 の順で試しながら、すべての順列を生成します。数値 x を選ぶたびに、次の処理を行います。
xを現在の経路の末尾に追加する。xを「使用済み」として記録する。- 次の位置を埋めるために再帰する。
再帰から戻った後、ある生徒は経路の末尾から x を削除するだけで、次の数値を試しました。
- このアルゴリズムが最初に得る順列は何ですか？6 通りすべての順列を得られますか？
- 1 つ上の層へ戻る前に、経路の末尾の数値を削除するだけで十分ですか？不十分な場合、ほかに何をする必要がありますか？理由も説明してください。
解答
-
最初に
[1, 2, 3]を得ますが、すべての順列を得ることはできません。戻るときに経路は短くなっても、 数値 1、2、3 の記録はすべて「使用済み」のままなので、それ以降の分岐では選べる数値がなくなります。 -
十分ではありません。経路の末尾から
xを削除した後、xを「未使用」に戻す必要もあります。 現在の経路と使用済みの記録が一緒になって探索状態を表しています。選択時に 2 か所を変更したので、戻るときにも両方を元に戻さなければ、 ほかの分岐で再びxを選べません。
2. 数値を選ぶ順序は重要か¶
ソート済み配列 [2, 3, 5] と目標値 5 が与えられ、各数値は何度でも選べます。
アルゴリズムでは、各探索経路の数値を小さい順にだけ並べるものとします。
- どのような異なる組合せを得られますか？
- 同じ数値の組を異なる順序で繰り返し探索する必要がないのはなぜですか？「小さい順」という制限にはどのような役割がありますか？
- 現在の経路が
[3]で、残りが 2 のとき、次の候補は 3 です。この時点で、同じ層の後ろにある候補をすべて調べずに終了できるのはなぜですか？
解答
-
異なる組合せは
[2, 3]と[5]です。 -
この問題では
[2, 3]と[3, 2]を同じ組合せとみなし、数値を選ぶ順序は答えに含めません。 経路の数値を小さい順に並べると定めることで、探索時に[3, 2]のような重複する組合せを最初から除外できます。 -
残りは 2 ですが、候補の 3 はすでに 2 より大きくなっています。配列はソート済みなので、 3 より後ろの候補はさらに大きく、どれも現在の組合せへ追加できません。そのため、この層の確認をそのまま終了できます。
3. 次のクイーンを置ける位置¶
4 × 4 のチェス盤に、行ごとにクイーンを置きます。行と列のインデックスはいずれも 0 から始まります。
現在、(0, 1) と (1, 3) にクイーンがあり、2 行目に次のクイーンを置こうとしています。
- 「同じ列」にあるため除外される列はどれですか？
- 残った列のうち、「同じ対角線」にあるため除外される位置はどれですか？
- 2 行目で試せる位置はどこですか？
解答
-
1 列目と 3 列目にはすでにクイーンがあるため、位置
(2, 1)と(2, 3)は除外されます。 -
残った位置のうち、
(2, 2)は(1, 3)と同じ対角線上にあるため、これも除外されます。 位置(2, 0)は、すでに置かれた 2 つのクイーンのどちらとも、同じ列にも同じ対角線上にもありません。 -
2 行目で試せる位置は
(2, 0)だけです。この段階では、現在の配置が条件を満たすことだけが分かります。この先でチェス盤を完成できなければ、戻って、それより前の別の選択を試す必要があります。
13.6.2 プログラミング演習¶
1. 重複要素のない全順列¶
整数配列 nums には少なくとも 1 つの要素があり、すべての要素が互いに異なります。
各要素を 1 回ずつ使って作れるすべての並びを列挙し、それぞれの並びを配列として返してください。
返す結果の中で、各順列を並べる順序は問いません。
バックトラッキングを使い、各位置の要素が現在の順列にすでに選ばれているかをブール配列で記録してください。
解法のヒント
- 再帰の深さは、順列の何番目の位置を埋めているかを表します
- 各層では、まだ使っていない要素だけを試します
- 経路の長さが
numsの長さに達したら、そのコピーを答えへ追加します