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!!
Answer
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]] ....