java で順列組み合わせアルゴリズムを実装する方法

2年 ago
結衣, 春花
1 minute

Javaでは、再帰を使用して、順列組み合わせアルゴリズムを実装できます。以下にサンプルコードを示します。

import java.util.ArrayList;
import java.util.List;
public class Combination {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(4);
int r = 3; // 选择r个元素进行组合
List<List<Integer>> combinations = combine(nums, r);
for (List<Integer> combination : combinations) {
for (int num : combination) {
System.out.print(num + " ");
}
System.out.println();
}
}
public static List<List<Integer>> combine(List<Integer> nums, int r) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(nums, r, 0, path, result);
return result;
}
private static void dfs(List<Integer> nums, int r, int start, List<Integer> path, List<List<Integer>> result) {
if (path.size() == r) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < nums.size(); i++) {
path.add(nums.get(i));
dfs(nums, r, i + 1, path, result);
path.remove(path.size() - 1);
}
}
}

上記コードでは、DFS(深さ優先探索)を用いて順列組み合わせを生成しています。 まずcombineメソッドが定義され、要素のリストと選択する要素数rを引数として受け取ります。 combineメソッドの内部では、結果リストresultと経路リストpathが作成されます。 その後、DFSを実行するためにdfsメソッドが呼び出されます。

DFS法では、対象とする要素のリストnums、選択する要素の数r、現在の探索開始位置start、現在のパスpath、結果リストresultを引数にとり、現在のパスの長さが選択する要素の数rと同じであれば、現在のパスを結果リストに追加し、終了します。そうでなければ、開始位置startから対象とする要素のリストnumsを順に探索し、現在の要素をパスのリストpathに追加し、DFS法を再帰的に呼び出して次要素の探索を続けます。探索開始位置は現在の位置の次の位置i+1です。再帰から戻った後に、現在の要素をパスのリストから削除し、次の要素の探索を続けます。最後に、結果リストを返します。

上記のコードを実行すると、出力が得られます。

1 2 3
1 2 4
1 3 4
2 3 4

与えられたリストから3つの要素を選択して並び替えた結果を表しています。

bannerAds