ある配列の [a, b, c] の組み合わせを格納した配列をつくりたい
[[a, b], [a, c], [b, c]]
数学的には 3C2になる
こちらを参考に実装してみる
public List<int[]> generate(int n, int r) { List<int[]> combinations = new ArrayList<>(); helper(combinations, new int[r], 0, n-1, 0); return combinations; } private void helper(List<int[]> combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else if (start <= end) { data[index] = start; helper(combinations, data, start + 1, end, index + 1); helper(combinations, data, start + 1, end, index); } }
再帰的な部分がよくわからないので具体例で3C2の場合を考えてみる
・index=0, start=0, end=2でhelperメソッドスタート ・data.lengthは2 →条件：index <> data.length && start <= end に入る ・処理：data[0] = 0 ・処理：index=1, start=1, end=2でhelperメソッド実行 → 条件：index <> data.length && start <= end に入る ・処理：data[1] = 1 ・処理：index=data.length, start=2, end=2でhelperメソッド実行 → 条件：index == data.length に入る ・処理：combinationsにdataを格納する [0, 1] ・処理：index=1, start=2, end=2 でhelperメソッド実行 →条件：index <> data.length && start <= end に入る ・処理：data[1] = 2 ・処理：index=2, start=3, end=2でhelperメソッド実行 →条件：index == data.length に入る ・処理：combinationsにdataを格納する [0, 2] ・処理：index=1, start=3, end=2 でhelperメソッド実行 →条件：いずれの条件にもはいらない ・処理：何もしない ・処理：index=0, start=1, end=2 でhelperメソッド実行 →条件：index <> data.length && start <= endに入る ・処理：data[0] = 1 ・処理：index=1, start=2, end=2 でhelperメソッド実行( →条件：index <> data.length && start <= endに入る ・処理：data[1] = 2 ・処理：index=2, start=3, end=2 でhelperメソッドを実行 →条件：index == data.lengthに入る ・処理：combinationsにdataを格納する [1, 2] ・処理：index=1, start=3, end=2 でhelperメソッドを実行 →条件：いずれの条件にもはいらない ・処理：何もしない
結果
[0, 1] [0, 2] [1, 2]
