Java 逆引き集 | 組み合わせ生成（combinatorics via stream） — テストデータ作成

Java Java
スポンサーリンク

ねらいと基本指針

テストデータを作るとき、組み合わせ（直積・順列・組合せ）を手早く生成できると検証の幅が一気に広がります。Java の Stream は「宣言的・短絡・遅延実行」が武器。巨大な結果を丸ごとメモリに載せず、必要な分だけ生成して使い切る設計にすると安全で速いです。重要な指針は、直積は map で展開、順列・組合せはインデックス走査で構築、そして limit などの短絡で爆発（N! や N^K）を抑えることです。

直積（Cartesian product）で入力パラメータを網羅

2集合の直積

2つのリストの全組み合わせは flatMap で自然に書けます。テストケースを「すべての選択肢 × すべてのオプション」で網羅する定番です。

List<String> colors = List.of("red", "blue");
List<String> sizes  = List.of("S", "M", "L");

record Case(String color, String size) {}

Stream<Case> product =
    colors.stream().flatMap(c ->
        sizes.stream().map(s -> new Case(c, s))
    );

List<Case> all = product.toList(); // 必要なら材質化
Java

flatMap の外側が「第一集合を走査」、内側が「第二集合を走査」し、ペア（またはタプル）を作ります。

3集合以上の直積

3つ以上は段階的に直積を重ねます。爆発しやすいので limit を前に置いて短絡し、材質化は慎重に。

List<String> colors = List.of("red", "blue");
List<String> sizes  = List.of("S", "M", "L");
List<String> materials = List.of("cotton", "poly");

record Case3(String color, String size, String material) {}

Stream<Case3> product3 =
    colors.stream().flatMap(c ->
        sizes.stream().flatMap(sz ->
            materials.stream().map(m -> new Case3(c, sz, m))
        )
    );

List<Case3> top = product3.limit(10).toList(); // 爆発対策に limit
Java

順列（permutations）で並び替えの全パターンを生成

固定長の完全順列（N!）

小さい N なら、インデックス走査と残集合の再帰で書けます。Stream で「都度要素を加えて展開」するのがコツです。

public static <T> Stream<List<T>> permutations(List<T> list) {
    if (list.isEmpty()) return Stream.of(List.of());
    return IntStream.range(0, list.size()).boxed().flatMap(i -> {
        T head = list.get(i);
        List<T> rest = new ArrayList<>(list);
        rest.remove(i);
        return permutations(rest).map(tail -> {
            List<T> out = new ArrayList<>(tail.size() + 1);
            out.add(head);
            out.addAll(tail);
            return out;
        });
    });
}

// 例
List<Integer> xs = List.of(1, 2, 3);
List<List<Integer>> all = permutations(xs).toList(); // 3! = 6
Java

完全順列は N! で爆発します。テストでは limit、findFirst、anyMatch を活用して「必要な分だけ使う」短絡設計が重要です。

部分順列（長さ k の並び）

要素から重複なしで長さ k の並びを作ります。先に「k-組合せ」を作って、それぞれの部分集合に対して順列を生成すると分かりやすいです。

public static <T> Stream<List<T>> kPermutations(List<T> list, int k) {
    return combinations(list, k).flatMap(ComboStreams::permutations);
}

// combinations は後述の関数を利用
Java

組合せ（combinations）で「順不同・重複なし」を生成

k-組合せ（nCk）

インデックスを前進させる反復で、順不同・重複なしの組合せを生成します。Stream と再帰を使うと短く書けます。

public static <T> Stream<List<T>> combinations(List<T> list, int k) {
    return combinationsFrom(list, 0, k);
}

private static <T> Stream<List<T>> combinationsFrom(List<T> list, int start, int k) {
    if (k == 0) return Stream.of(List.of());
    if (start >= list.size()) return Stream.empty();
    return IntStream.range(start, list.size()).boxed().flatMap(i -> {
        T head = list.get(i);
        return combinationsFrom(list, i + 1, k - 1).map(tail -> {
            List<T> out = new ArrayList<>(tail.size() + 1);
            out.add(head);
            out.addAll(tail);
            return out;
        });
    });
}

// 例
List<String> items = List.of("A", "B", "C", "D");
List<List<String>> choose2 = combinations(items, 2).toList(); // [A,B], [A,C], ...
Java

可変長の全組合せ（パワーセット）

全ての部分集合（空集合から元集合まで）を生成します。テストで「任意フラグの有無」を網羅したい時などに便利ですが、2^N で爆発するため短絡が必須です。

public static <T> Stream<List<T>> powerSet(List<T> list) {
    return IntStream.rangeClosed(0, list.size())
        .boxed()
        .flatMap(k -> combinations(list, k));
}
Java

実例で体感するテストデータ生成

入力×環境×権限の直積で E2E テストケースを作る

3軸の直積を生成し、一部だけ実行して結果をファイルへ逐次出力します。材質化せず forEach で外部へ流すのが大量ケース対策の基本です。

record Case(String input, String env, String role) {}

List<String> inputs = List.of("empty", "normal", "max");
List<String> envs   = List.of("dev", "stg", "prod");
List<String> roles  = List.of("guest", "user", "admin");

Stream<Case> cases =
    inputs.stream().flatMap(i ->
        envs.stream().flatMap(e ->
            roles.stream().map(r -> new Case(i, e, r))
        )
    );

try (var w = java.nio.file.Files.newBufferedWriter(java.nio.file.Paths.get("cases.txt"))) {
    cases.limit(10_000).forEach(c -> {
        try { w.write(c.input() + "," + c.env() + "," + c.role()); w.newLine(); }
        catch (java.io.IOException ex) { throw new java.io.UncheckedIOException(ex); }
    });
}
Java

増幅された入力の順列で並び依存バグを炙り出す

同じ値が複数入る拡張リストを作ってから順列を流し、順序依存の欠陥を探します。重複順列が多すぎる場合は distinct でユニーク化します。

List<Integer> base = List.of(1, 2, 3);
List<Integer> amplified = new ArrayList<>(base);
amplified.addAll(base); // 1,2,3,1,2,3

permutations(amplified)
    .map(seq -> seq.stream().map(Object::toString).collect(java.util.stream.Collectors.joining(",")))
    .distinct()          // 重複順列を削る
    .limit(1000)         // 爆発対策
    .forEach(System.out::println);
Java

入力候補から k-組合せを生成して API の引数網羅

API のオプション引数（オンオフや選択肢）を k-組合せで作り、順列にせず「順不同」で網羅します。スイッチ群のテストに有効です。

List<String> opts = List.of("A", "B", "C", "D");
combinations(opts, 3)
    .map(c -> String.join("+", c))
    .forEach(System.out::println);
Java

深掘り：爆発対策・正しさ・性能の勘所

爆発（N!・2^N・N^K）を制御する短絡

組み合わせ生成は増え方が急激です。limit、findFirst、anyMatch、takeWhile を上流に置いて「必要な分だけ」取り出すのが最重要ポイントです。材質化（toList/toSet）は小規模に限定し、基本は逐次出力（forEach でファイルやネット）に切り替えます。

再帰生成のメモリ・GC負荷

再帰で List を新しく作るため、一時オブジェクトが増えます。テストで長時間回すなら、出力先へ即書き出し（forEach）の形にして中間を捨てる設計にします。並列は生成順序の依存と分割困難のため一般に効果が薄く、まずは順次で確実に。

不変性と副作用ゼロの部品化

生成関数（permutations/combinations）は入力を変更せず、出力を新規作成に徹します。副作用を混ぜないことで、再利用性とテストの安定性が上がります。条件付き生成が必要なら、生成の前後で filter を掛けて範囲を削るのが安全です。

直積は map＋flatMap、順列・組合せはインデックス走査

直積は「外側を走査して内側を展開」する単純な合成。順列・組合せは「未使用要素の選択」と「先へ進むインデックス（または残集合）」が正しさの鍵です。順不同・重複なしの保証は「インデックスを前へだけ進める」ことで担保します。

テンプレート（すぐ流用できる雛形）

2集合直積

public static <A,B,R> Stream<R> product(List<A> as, List<B> bs, java.util.function.BiFunction<A,B,R> f) {
    return as.stream().flatMap(a -> bs.stream().map(b -> f.apply(a, b)));
}
Java

k-組合せ

public static <T> Stream<List<T>> combinations(List<T> list, int k) {
    return combinationsFrom(list, 0, k);
}
private static <T> Stream<List<T>> combinationsFrom(List<T> list, int start, int k) {
    if (k == 0) return Stream.of(List.of());
    if (start >= list.size()) return Stream.empty();
    return IntStream.range(start, list.size()).boxed().flatMap(i -> {
        T head = list.get(i);
        return combinationsFrom(list, i + 1, k - 1).map(tail -> {
            List<T> out = new ArrayList<>(tail.size() + 1);
            out.add(head); out.addAll(tail); return out;
        });
    });
}
Java

完全順列

public static <T> Stream<List<T>> permutations(List<T> list) {
    if (list.isEmpty()) return Stream.of(List.of());
    return IntStream.range(0, list.size()).boxed().flatMap(i -> {
        T head = list.get(i);
        List<T> rest = new ArrayList<>(list); rest.remove(i);
        return permutations(rest).map(tail -> {
            List<T> out = new ArrayList<>(tail.size() + 1);
            out.add(head); out.addAll(tail); return out;
        });
    });
}
Java

パワーセット

public static <T> Stream<List<T>> powerSet(List<T> list) {
    return IntStream.rangeClosed(0, list.size()).boxed()
        .flatMap(k -> combinations(list, k));
}
Java

まとめ

Stream を使えば、直積・順列・組合せを、宣言的に短く安全に生成できます。直積は flatMap の展開、順列・組合せはインデックス前進の構成が基本。爆発的増加に対しては limit や逐次出力でメモリと時間を制御し、材質化は小さく。副作用ゼロの関数として部品化すれば、テストデータ作成の再利用性と保守性が飛躍的に上がります。

スポンサーリンク
タイトルとURLをコピーしました