Questions

  1. Home
  2. Questions

Algorithm to extract combinations of array



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]]
....
Source: stackoverflow

Recent Comments