How to get different grouping combinations from a

Question

I'm working on a problem where I want to group a list by two's and get all possible combinations. for example: for the list [A,B,C,D]; I'm trying to create a method that will give me the ff:

   A and BCD
    B and ACD
    C and ABD
    D and ABC
    AB and CD
    AC and BD
    AD and BC

etc...

I know that recursion is the answer but I don't know where to start. Can someone point me to the right direction?

My attempt so far:

List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

    for (int x = 1; x < list.size() - 1; x++) {  //how many elements in one group
        for (int i = 0; i < list.size(); i++) {   //get first group..
            List<Integer> chosenIndices = new ArrayList<>();   //?..
            chosenIndices.add(i); // good for one element grouping only.. 
            List<String> firstGroup = getFirstGroup(list, chosenIndices); //method to pick chosenindices
            List<String> secondGroup = getRestofList(list, chosenIndices);  //method to exclude chosenIndices
            System.out.println(firstGroup + ": " + secondGroup);
        }

    }

this takes care of the combination where the first group contains one element but I can't figure out how to get the next iteration and come up with a list of two elements for the first group. I hope this makes sense.

Answer 1

My first answer maybe was useful, but it worked bad. Sorry.

Here is another example. It is based on the rules of combinatorics:

(n, k) = (n - 1, k - 1) + (n - 1, k)

where n - is the number of elements total, and k is the number of elements is group

@Test
    public void test() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

        List<String> result = new ArrayList<>();

        for (int i = 1; i < list.size() + 1; i++) {
            combine(list, result, i);
        }

        System.out.println(result);
    }

    public static void combine(List<String> list, List<String> result, int k) {
        if (k > list.size())
            return;

        // calculate and print the possible combinations
        // e.g. c(4,2)
        int ncr = fact(list.size()) / fact(list.size() - k) / fact(k);
        System.out.println(String.format("C(%s, %s). Combinations nbr = %s", list.size(), k, ncr));

        // get the combine by index
        // e.g. 01 --> AB , 23 --> CD
        int combination[] = new int[k];

        // position of current index
        int r = 0;
        int index = 0;

        while (r >= 0) {
            // for r = 0 ==> index < (4+ (0 - 2)) = 2
            if (index <= (list.size() + (r - k))) {
                combination[r] = index;

                // if we are at the last position print and increase the index
                if (r == k - 1) {
                    //do something with the combine e.g. add to list or print
                    add(combination, list, result);
                    index++;
                } else {
                    // select index for next position
                    index = combination[r] + 1;
                    r++;
                }
            } else {
                r--;
                if (r > 0)
                    index = combination[r] + 1;
                else
                    index = combination[0] + 1;
            }
        }
    }

    private static int fact(int n) {
        if (n == 0)
            return 1;
        else
            return n * fact(n - 1);
    }

    private static void add(int[] combination, List<String> elements, List<String> result) {
        String output = "";
        for (int i = 0; i < combination.length; i++) {
            output += elements.get(combination[i]);
        }

        result.add(output);
    }

The output will be:

C(4, 1). Combinations nbr = 4
C(4, 2). Combinations nbr = 6
C(4, 3). Combinations nbr = 4
C(4, 4). Combinations nbr = 1
[A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD]