毎日のアルゴリズム: 完全順列問題

[[435870]]

繰り返しのない数字のシーケンスが与えられた場合、そのシーケンスのすべての可能な順列を返します。

例：

入力: [1,2,3]
出力：
 [
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
 ]

この質問はバックトラッキングアルゴリズムの典型的な応用シナリオである。

1. アルゴリズム戦略

バックトラッキングアルゴリズムは、検索方法とヒューリスティックメソッドです。各ステップで選択を行います。この選択では期待される結果が得られないことが判明すると、バックトラックして新しい選択を行います。深さ優先探索はバックトラッキングアルゴリズムの考え方を使用します。

2. 適用可能なシナリオ

バックトラッキングアルゴリズムは非常に単純で、解決策が見つかるまで試行を続けるだけです。このアルゴリズムの考え方により、幅探索問題、つまり一連の可能な解決策から要件を満たす解決策を選択する問題を解決するためによく使用されます。

3. コードの実装

配列[1, 2, 3]の完全な順列は次のように書くことができます。

まず、1 から始まる完全な順列を書きます。これらは、[1, 2, 3]、[1, 3, 2] であり、これは 1 + [2, 3] の完全な順列です。

2 から始まるすべての順列を書き出してみましょう。[2, 1, 3]、[2, 3, 1] は、2 + [1, 3] の完全な順列です。

最後に、3 で始まる順列をすべて書き出します。これらは [3, 1, 2]、[3, 2, 1] であり、これらは 3 + [1, 2] のすべての順列です。

それはバックトラッキングの考え方であり、列挙検索に多少似ています。すべての解決策を列挙し、期待を満たすものを見つけます。考えられる解決策を定期的にすべて列挙し、漏れや重複を避けるために、問題解決のプロセスを複数の段階に分けます。各ステージで、私たちは分岐点に直面します。ランダムにいずれかの道を選択します。この道が実行可能ではない (期待される解決策を満たしていない) とわかったら、前の分岐点に戻り、別の道を選択して続行します。

これは明らかに再帰的な構造です。

再帰の終了条件は、順列内の十分な数が選択されることです。そのため、現在のプログラムが再帰するレベルを示す変数が必要です。この変数を深さまたはインデックスと呼びます。これは、完全な順列内のインデックスを使用して数を決定する必要があることを意味します。
used(object): 数字が選択されているかどうかを示すために使用します。数字(num)が選択されている場合は、used[num] = true に設定します。このように、次の位置を考えるとき、O(1)の時間計算量で数字が選択されたかどうかを判定できます。これは、「スペースを時間と交換する」というアイデアです。

 let permute = function (nums) {
    // 配列を使用してすべての可能な順列を保存します
    res = [] とします
    （数値の長さ === 0）の場合{
戻り値
    }
    使用 = {}、パス = []
    dfs(数値、数値の長さ、0、パス、使用、res)
戻り値
}
 dfs = function (nums, len, depth, path, used, res) とします。
    // すべての数字が入力されています
    深さ === 長さの場合{
        res.push([...パス])
戻る 
    }
 (i = 0; i < len; i++)の場合{
        もし (!used[i]) {
            //配列を動的に維持する
            パス.push(数値[i])
            使用済み[i] =真 
            // 次の数字を再帰的に入力し続ける
            dfs(数値、長さ、深さ + 1、パス、使用、解像度)
            // 操作を元に戻す
            使用[i] =偽 
            パス.pop()
        } 
       
    }
 }