全列挙問題における効率的な解法

DFS（深さ優先探索）の実装

再帰を用いたバックトラッキングアプローチで、以下の特徴を持つ：

import java.util.*;

public class PermutacaoDFS {
    public List<List<Integer>> gerarPermutacoes(int[] dados) {
        List<List<Integer>> resultado = new ArrayList<>();
        boolean[] visitado = new boolean[dados.length];
        dfs(dados, visitado, new ArrayList<>(), resultado);
        return resultado;
    }

    private void dfs(int[] dados, boolean[] visitado, 
                    List<Integer> caminho, List<List<Integer>> resultado) {
        if (caminho.size() == dados.length) {
            resultado.add(new ArrayList<>(caminho));
            return;
        }

        for (int i = 0; i < dados.length; i++) {
            if (visitado[i]) continue;
            
            // 重複要素の処理
            if (i > 0 && dados[i] == dados[i-1] && !visitado[i-1]) 
                continue;
            
            caminho.add(dados[i]);
            visitado[i] = true;
            dfs(dados, visitado, caminho, resultado);
            caminho.remove(caminho.size() - 1);
            visitado[i] = false;
        }
    }
}

Next Permutationアルゴリズム

辞書順で次の順列を生成する効率的な方法：

public class ProximaPermutacao {
    public void proximaPermutacao(int[] sequencia) {
        int n = sequencia.length;
        int i = n - 2;
        
        while (i >= 0 && sequencia[i] >= sequencia[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && sequencia[j] <= sequencia[i]) {
                j--;
            }
            trocar(sequencia, i, j);
        }
        
        inverter(sequencia, i + 1, n - 1);
    }

    private void trocar(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    private void inverter(int[] arr, int inicio, int fim) {
        while (inicio < fim) {
            trocar(arr, inicio++, fim--);
        }
    }
}

両手法の比較表

選択ガイドライン

• 制約条件が多い場合 → DFSを選択
• 大規模データ(n>12) → Next Permutationを選択
• 重複要素がある場合 → Next Permutationが有利
• k番目の順列が必要 → Next Permutationが適切