Java 组合生成

Question

我想看看 java 是否有一些我可以利用的组合学特征。我想要一个动态列表，并且以一种干净的方式让 java 生成所有组合。

给定一个对象列表，比如下面的字符串。是否有一个简单的 way/clean way/preferably 已经内置到核心 java 中的东西来生成项目的所有组合？例如如果我有：

List<String> items = new ArrayList<String>();
items.add("a");
items.add("b");
List<List<String>> result = generateCombinationOf(items);

我希望结果包含：{{}, {"a"}, {"b"}, {"a", "b"}}

旁注： 过去我能够在 Mathematica 中生成这样的列表。我有一个我想利用 java 的业余项目，我希望尽可能避免与 Mathematica 集成，但如果我找不到像上面那样容易获得的一些功能，我会这样做。

Answer 1

试试这个。

static void generateCombinationOf(List<String> items,
        List<String> selected, int index, List<List<String>> result) {
    if (index >= items.size()) {
        result.add(new ArrayList<>(selected));
    } else {
        generateCombinationOf(items, selected, index + 1, result);
        selected.add(items.get(index));
        generateCombinationOf(items, selected, index + 1, result);
        selected.remove(selected.size() - 1);
    }
}

static List<List<String>> generateCombinationOf(List<String> items) {
    List<List<String>> result = new ArrayList<>();
    List<String> selected = new ArrayList<>();
    generateCombinationOf(items, selected, 0, result);
    return result;
}

和

System.out.println(generateCombinationOf(Arrays.asList("a", "b")));

结果

[[], [b], [a], [a, b]]

非递归版本

static List<List<String>> generateCombinationOf(List<String> list) {
    List<List<String>> result = new ArrayList<>();
    for (int i = 0, max = 1 << list.size(); i < max; ++i) {
        List<String> comb = new ArrayList<>();
        for (int j = 0, k = i; k > 0; ++j, k >>= 1)
            if ((k & 1) == 1)
                comb.add(list.get(j));
        result.add(comb);
    }
    return result;
}

Java 组合生成

Java Combination Generation

java

combinations

permutation

combinatorics