c++ - Algorithm that can create all combinations and all groups of those combinations

Question

Let's say I have a set of elements S = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

I would like to create combinations of 3 and group them in a way such that no number appears in more than one combination.

Here is an example: { {3, 7, 9}, {1, 2, 4}, {5, 6, 8} }

The order of the numbers in the groups does not matter, nor does the order of the groups in the entire example.

In short, I want every possible group combination from every possible combination in the original set, excluding the ones that have a number appearing in multiple groups.

My question: is this actually feasible in terms of run time and memory? My sample sizes could be somewhere around 30-50 numbers.

If so, what is the best way to create this algorithm? Would it be best to create all possible combinations, and choose the groups only if the number hasn't already appeared?

I'm writing this in Qt 5.6, which is a C++ based framework.

Answer 1

You can do this recursively, and avoid duplicates, if you keep the first element fixed in each recursion, and only make groups of 3 with the values in order, eg:

{1,2,3,4,5,6,7,8,9}

Put the lowest element in the first spot (a), and keep it there:

{a,b,c} = {1, *, *}

For the second spot (b), iterate over every value from the second-lowest to the second-highest:

{a,b,c} = {1, 2~8, *}

For the third spot (c), iterate over every value higher than the second value:

{1, 2~8, b+1~9}

Then recurse with the rest of the values.

{1,2,3} {4,5,6} {7,8,9}
{1,2,3} {4,5,7} {6,8,9}
{1,2,3} {4,5,8} {6,7,9}
{1,2,3} {4,5,9} {6,7,8}
{1,2,3} {4,6,7} {5,8,9}
{1,2,3} {4,6,8} {5,7,9}
{1,2,3} {4,6,9} {5,7,8}
{1,2,3} {4,7,8} {5,6,9}
{1,2,3} {4,7,9} {5,6,8}
{1,2,3} {4,8,9} {5,6,7}
{1,2,4} {3,5,6} {7,8,9}
...
{1,8,9} {2,6,7} {3,4,5}

Wen I say "in order", that doesn't have to be any specific order (numerical, alphabetical...), it can just be the original order of the input. You can avoid having to re-sort the input of each recursion if you make sure to pass the rest of the values on to the next recursion in the order you received them.

---

A run-through of the recursion:

Let's say you get the input {1,2,3,4,5,6,7,8,9}. As the first element in the group, you take the first element from the input, and for the other two elements, you iterate over the other values:

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,2,7}
{1,2,8}
{1,2,9}
{1,3,4}
{1,3,5}
{1,3,6}
...
{1,8,9}

making sure the third element always comes after the second element, to avoid duplicates like:

{1,3,5} ⇆ {1,5,3}

Now, let's say that at a certain point, you've selected this as the first group:

{1,3,7}

You then pass the rest of the values onto the next recursion:

{2,4,5,6,8,9}

In this recursion, you apply the same rules as for the first group: take the first element as the first element in the group and keep it there, and iterate over the other values for the second and third element:

{2,4,5}
{2,4,6}
{2,4,8}
{2,4,9}
{2,5,6}
{2,5,8}
{2,5,9}
{2,6,7}
...
{2,8,9}

Now, let's say that at a certain point, you've selected this as the second group:

{2,5,6}

You then pass the rest of the values onto the next recursion:

{4,8,9}

And since this is the last group, there is only one possibility, and so this particular recursion would end in the combination:

{1,3,7} {2,5,6} {4,8,9}

As you see, you don't have to sort the values at any point, as long as you pass them onto the next recursion in the order you recevied them. So if you receive e.g.:

{q,w,e,r,t,y,u,i,o}

and you select from this the group:

{q,r,u}

then you should pass on:

{w,e,t,y,i,o}

---

Here's a JavaScript snippet which demonstrates the method; it returns a 3D array with combinations of groups of elements.
(The filter function creates a copy of the input array, with elements 0, i and j removed.)

function clone2D(array) {
    var clone = [];
    for (var i = 0; i < array.length; i++) clone.push(array[i].slice());
    return clone;
}

function groupThree(input) {
    var result = [], combination = [];
    group(input, 0);
    return result;

    function group(input, step) {
        combination[step] = [input[0]];
        for (var i = 1; i < input.length - 1; i++) {
            combination[step][1] = input[i];
            for (var j = i + 1; j < input.length; j++) {
                combination[step][2] = input[j];
                if (input.length > 3) {
                    var rest = input.filter(function(elem, index) {
                        return index && index != i && index != j;
                    });
                    group(rest, step + 1);
                }
                else result.push(clone2D(combination));
            }
        }
    }
}

var result = groupThree([1,2,3,4,5,6,7,8,9]);
for (var r in result) document.write(JSON.stringify(result[r]) + "<br>");