Unique Permutations Algorithm Analysis

📋 アルゴリズム概要

重複要素を含む配列から一意な順列を生成するアルゴリズムです。バックトラッキングと重複スキップ技法を使用します。

計算量分析：
• 時間計算量: O(n! × n) - 最悪の場合
• 空間計算量: O(n) - 再帰スタック + 補助配列

🎯 Step 1: 入力配列のソート

重複要素を隣接させるため、まず配列をソートします。

例: [1,1,2] の処理

ソート前:

1

2

ソート後:

1

2

同じ値の要素が隣接配置されます

🌳 Step 2: バックトラッキング探索木

各レベルで利用可能な要素を選択し、重複をスキップしながら順列を構築します。

Level 0 (ROOT)

[]

Level 1

[1]

[1] (スキップ)

[2]

Level 2

[1,1]

[1,2]

[2,1]

Level 3 (完成)

[1,1,2]

[1,2,1]

[2,1,1]

⚡ Step 3: 重複スキップのメカニズム

同じ値を持つ要素群で、使用順序を制御することで重複順列を防ぎます。

🚫 重複スキップ条件:

                        if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) { continue; //
                        この選択をスキップ }
                    

条件の意味:

nums[i] === nums[i-1]: 前の要素と同じ値
!used[i-1]: 前の同じ値の要素がまだ未使用
→ 同じ値の要素群は順番に使用することを強制

具体例: [1a, 1b] の使用順序制御

✅ 許可されるパターン:

1a

→

1b

: 順番通り

❌ スキップされるパターン:

1a

→

1b

: 1aが未使用なので1bはスキップ

🔄 Step 4: バックトラッキングの動作

選択→探索→取り消しのサイクルで全パターンを効率的に探索します。

バックトラッキングの流れ

1. 要素選択:

1

2

current = [1], used = [true, false, false]

2. 次レベル探索:

1

2

current = [1,1], used = [true, true, false]

3. 完成 & バックトラック:

1

2

result.push([1,1,2]) → バックトラック開始

4. 状態復元: ↩️

1

2

current = [1], used = [true, false, false]

📊 最終結果

入力 [1,1,2] に対する全ての一意な順列:

[1, 1, 2]

[1, 2, 1]

[2, 1, 1]

総数: 3個 (重複なし版では6個 → 重複除去により3個)

⚙️ アルゴリズムの効率性

🎯 最適化ポイント:

事前ソート: O(n log n) - 重複スキップを可能にする
early pruning: 無効な枝を早期に切る
in-place操作: 追加の配列コピーを最小限に
used配列: O(1)でのアクセス・更新

パフォーマンス比較

手法	時間計算量	空間計算量	重複処理
全順列生成 + Set除去	O(n! × n)	O(n! × n)	後処理
本手法	O(n! × n)	O(n)	事前回避

🎮 インタラクティブデモ

異なる入力での動作を確認してみましょう:

🔄 Unique Permutations Algorithm Analysis