Algorithm to extract combinations of array-CodePudding

I'm stuck with the problem to find possible combinations in an array. Currently, i solving this problem using Java Programming language. Here is the example:

String[] array = new String[]{"AAA", "BBB", "CCC", "DDD"};

And here is the output that i want, so i can solve the fundamental issues:

//possibility number 1
["AAA"],["BBB"],["CCC"],["DDD"]
//possibility number 2
["AAA","BBB"],["CCC"],["DDD"]
//possibility number 3
["AAA","BBB","CCC"],["DDD"]
//possibility number 4
["AAA"],["BBB","CCC"],["DDD"]
//possibility number 5
["AAA"],["BBB"],["CCC","DDD"]
//possibility number 6
["AAA"],["BBB","CCC","DDD"]
//etc.

The purpose is to generate combinations with sorted conditions as pairs of array like that. How to solve this? I need the algorithm, if can provide some example in another programming language its still very helpful!!

CodePudding user response：

The most natural way is using recursion where you assume output is empty

[
]

then you add a new list with one group with one element

[[[A]]
]

then for every previous group simply add on every position or at the end

[[[A,B]]
,[[A],[B]]
]

and (more simple than @kcsquared link) you can write

static <T> List<List<List<T>>> partitions(List<T> set) {
    // current element
    T element = set.get(0);

    if(set.size() == 1)
        return singletonList(singletonList(singletonList(element)));

    List<List<List<T>>> current = new ArrayList<>();

    // add on every previous
    for (List<List<T>> p : partitions(set.subList(1, set.size()))) {
        // every candidate group to place
        for(int i = 0; i < p.size(); i  ) {
            List<List<T>> b = new ArrayList<>(p);
            b.add(i, new ArrayList<>(b.remove(i)));
            b.get(i).add(element);
            current.add(b);
        }
        // add singleton
        List<List<T>> b = new ArrayList<>(p);
        b.add(singletonList(element));
        current.add(b);
    }

    return current;
}

if you run

for (List<List<String>> x : partitions(List.of("AAA", "BBB", "CCC", "DDD")))
    System.out.println(x);

you get

[[DDD, CCC, BBB, AAA]]
[[DDD, CCC, BBB], [AAA]]
[[DDD, CCC, AAA], [BBB]]
[[DDD, CCC], [BBB, AAA]]
[[DDD, CCC], [BBB], [AAA]]
[[DDD, BBB, AAA], [CCC]]
[[DDD, BBB], [CCC, AAA]]
[[DDD, BBB], [CCC], [AAA]]
[[DDD, AAA], [CCC, BBB]]
[[DDD], [CCC, BBB, AAA]]
[[DDD], [CCC, BBB], [AAA]]
[[DDD, AAA], [CCC], [BBB]]
[[DDD], [CCC, AAA], [BBB]]
[[DDD], [CCC], [BBB, AAA]]
[[DDD], [CCC], [BBB], [AAA]]

(you can reverse input list or output list or any other order you wish)

E.g. change

// last element
T element = set.get(set.size() - 1);

and

...: partitions(set.subList(0, set.size() - 1))

to get

[[AAA, BBB, CCC, DDD]]
[[AAA, BBB, CCC], [DDD]]
[[AAA, BBB, DDD], [CCC]]
[[AAA, BBB], [CCC, DDD]]
....