CODEWITHSUNDEEP
javacombinationspermutationcombinatorics
James Oravec
James Oravec

Reputation: 20391

Java Combination Generation

I'm looking to see if java has some combinatorics features that I can utilize. I want to have a dynamic list, and in a clean way, have java generate all combinations.

Given a list of objects, such as strings below. Is there an easy way/clean way/preferably something already built into core java to generate all combinations of the items? e.g. If I had:

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

I desire for results to contain: {{}, {"a"}, {"b"}, {"a", "b"}}

Side note: I was able to generate lists like this in mathematica in the past. I have a side project where I want to utilize java and I'm hoping to avoid integrating with mathematica if at all possible, but will if I can't find some features like the above easily available.

Upvotes: 1

Views: 1054

Answers (1)

user4910279
user4910279

Reputation:

Try this.

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;
}

and

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

result

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

non-recursive version

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;
}

Upvotes: 1

Related Questions