javaで全排列を再帰的に求めるアルゴリズムの適用方法

全排列は組み合わせ数学の古典的な問題で、再帰アルゴリズムはこの問題を非常に上手く解決できます。以下は全排列を再帰アルゴリズムで実装したJavaの例の1つです。

import java.util.ArrayList;
public class Permutations {
public static void main(String[] args) {
int[] nums = {1, 2, 3};
ArrayList<ArrayList<Integer>> result = permute(nums);
System.out.println(result);
}
public static ArrayList<ArrayList<Integer>> permute(int[] nums) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
ArrayList<Integer> tempList = new ArrayList<>();
permuteHelper(nums, tempList, result);
return result;
}
private static void permuteHelper(int[] nums, ArrayList<Integer> tempList, ArrayList<ArrayList<Integer>> result) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (tempList.contains(nums[i])) {
continue;
}
tempList.add(nums[i]);
permuteHelper(nums, tempList, result);
tempList.remove(tempList.size() - 1);
}
}
}
}

コード内でpermute()メソッドはエントリーメソッドですが、これは空の結果リストと空の一時リストを作成し、permuteHelper()メソッドを再帰的に呼び出します。permuteHelper()メソッドは3つのパラメータを取ります。これは元となる数値の配列nums、一時リストtempList、および結果リストresultです。

permuteHelper()関数内で、まず仮リストのサイズが基本配列と同じであるかどうかをチェックします。同じである場合は仮リストを結果リストに追加します。異なる場合は、基本配列の各要素について、仮リストにすでに含まれている場合はスキップし、含まれていない場合は仮リストに追加し、permuteHelper()を再帰的に呼び出して仮リストの最後尾の要素を削除して次に進みます。

一時的リストの大きさが元の配列の大きさと等しくなった時点ですべての順列が生成されたことを示し、一時的リストを結果リストに追加して、結果リストを返却する。

ネイティブ実装の Java 再帰アルゴリズムの完全な並べ替えの一例は上記の通りです。このアルゴリズムの時間計算量は O(n!) であり、ここで n は元の配列のサイズです。