Javaにおけるリスト要素の順列生成

与えられたリストの全要素を使用する順列（全ての可能な並び順）を生成する方法について解説します。ここでは再帰的アプローチを用いた実装を示します。

実装コード

import java.util.ArrayList;
import java.util.List;

public class PermutationGenerator {
    
    public static List<List<Integer>> generateAllPermutations(List<Integer> elements) {
        List<List<Integer>> permutationResults = new ArrayList<>();
        List<Integer> currentSequence = new ArrayList<>();
        boolean[] usedElements = new boolean[elements.size()];
        
        buildPermutations(elements, usedElements, currentSequence, permutationResults);
        return permutationResults;
    }
    
    private static void buildPermutations(List<Integer> sourceList,
                                         boolean[] usageFlags,
                                         List<Integer> ongoingPermutation,
                                         List<List<Integer>> resultCollector) {
        
        if (ongoingPermutation.size() == sourceList.size()) {
            resultCollector.add(new ArrayList<>(ongoingPermutation));
            return;
        }
        
        for (int idx = 0; idx < sourceList.size(); idx++) {
            if (!usageFlags[idx]) {
                usageFlags[idx] = true;
                ongoingPermutation.add(sourceList.get(idx));
                
                buildPermutations(sourceList, usageFlags, ongoingPermutation, resultCollector);
                
                ongoingPermutation.remove(ongoingPermutation.size() - 1);
                usageFlags[idx] = false;
            }
        }
    }
    
    public static void main(String[] args) {
        List<Integer> sampleData = new ArrayList<>();
        sampleData.add(5);
        sampleData.add(7);
        sampleData.add(9);
        
        List<List<Integer>> allPermutations = generateAllPermutations(sampleData);
        
        for (List<Integer> singlePermutation : allPermutations) {
            System.out.println(singlePermutation);
        }
    }
}

アルゴリズムの説明

この実装では、以下の主要コンポーネントを使用しています：

• usageFlags配列: 各要素が現在の順列構築で使用済みかどうかを追跡します
• ongoingPermutationリスト: 構築中の現在の順列を保持します
• resultCollectorリスト: 完成した全ての順列を保存します

アルゴリズムの動作原理：

1. 基底ケース：現在の順列が入力リストと同サイズになった場合、それを結果コレクションに追加
2. 再帰ケース：未使用の各要素について、それを現在順列に追加し、使用済みフラグを設定して再帰呼び出し
3. バックトラッキング：再帰から戻った後、最後の要素を削除し使用フラグを解除

実行例

入力リスト [5, 7, 9] に対する出力：

[5, 7, 9]
[5, 9, 7]
[7, 5, 9]
[7, 9, 5]
[9, 5, 7]
[9, 7, 5]

計算量

n個の異なる要素に対する順列数はn!（nの階乗）です。このアルゴリズムの時間計算量はO(n×n!)となり、全順列の生成と各順列の構築にかかる時間を反映しています。空間計算量は再帰呼び出しスタックを含めてO(n)です。