順列生成アルゴリズムの解析と可視化

🎯 アルゴリズムの概要

バックトラッキングを用いた順列生成アルゴリズムは、以下の手順で動作します：

1. 初期化: 結果配列、現在の順列、使用フラグ配列を準備
2. 再帰的構築: 各位置に未使用の要素を順次配置
3. バックトラック: 完成した順列を保存後、状態を復元して次の組み合わせを探索

🌳 実行トレースの可視化 (nums = [1, 2, 3])

Level 0 (空の状態)
1
2
3
現在の順列: []
使用フラグ: [false, false, false]

📊 決定木の構造

Root
[]
Level 1
[1]
[2]
[3]
Level 2
[1,2]
[1,3]
[2,1]
[2,3]
[3,1]
[3,2]
Level 3 (完成した順列)
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

💻 ステップ別コード実行

1. 関数の初期化

function permute(nums: number[]): number[][] { const result: number[][] = []; // 結果を格納 const currentPermutation: number[] = []; // 現在構築中の順列 const used: boolean[] = new Array(nums.length).fill(false); // 使用フラグ

2. バックトラッキング関数

function backtrack(nums, currentPermutation, used, result): void { // ベースケース: 順列が完成したか確認 if (currentPermutation.length === nums.length) { result.push([...currentPermutation]); // コピーして保存 return; } // 各要素を試行 for (let i = 0; i < nums.length; i++) { if (used[i]) continue; // 使用済みはスキップ // 要素を追加 currentPermutation.push(nums[i]); used[i] = true; // 再帰呼び出し backtrack(nums, currentPermutation, used, result); // バックトラック currentPermutation.pop(); used[i] = false; } }

⚡ 計算量解析

時間計算量: O(n! × n)

理由:

  • n個の要素から作れる順列の数: n!
  • 各順列をコピーする時間: O(n)
  • 総時間計算量: n! × n

空間計算量: O(n)

理由:

  • 再帰スタックの深さ: O(n)
  • used配列のサイズ: O(n)
  • currentPermutation配列: O(n)

🔍 具体例での実行流れ (nums = [1, 2])

Step 1: backtrack([], [false, false])
→ i=0を選択: currentPermutation=[1], used=[true, false]
Step 2: backtrack([1], [true, false])
→ i=1を選択: currentPermutation=[1,2], used=[true, true]
Step 3: backtrack([1,2], [true, true])
→ 長さ2に到達、結果に[1,2]を追加
Step 4: バックトラック
→ currentPermutation=[1], used=[true, false]
Step 5: さらにバックトラック
→ currentPermutation=[], used=[false, false]
Step 6: i=1を選択
→ currentPermutation=[2], used=[false, true]
Step 7: i=0を選択
→ currentPermutation=[2,1], used=[true, true]
→ 結果に[2,1]を追加

🚀 最適化のポイント

1. スプレッド演算子によるコピー
[...currentPermutation] で配列の浅いコピーを高速作成
2. boolean配列による状態管理
Setより高速なO(1)アクセスでメモリ効率も良い
3. インプレース操作
push/popを使用してメモリ使用量を最小化
4. 早期終了
使用済み要素はcontinueで即座にスキップ