What kind of algorithm do I need?

Question

I'm trying to figure out all the different ways I can create groups of 4 from 6 objects using objective-c.

For example, if I had the following objects: a, b, c, d, e, f

Then I could create groups like

a, b, c, d

b, c, d, e

a, d, e, f

and so on. Order doesn't matter. If I wanted to figure out all the different possibilities, what kind of algorithm do I need? At first I was thinking of permutations, but I don't think that's it. I think there might be something faster or more appropriate, but I forgot what it's called.

Answer 1

If you need to select 4 different objects in all possible ways, it means you need to remove ('not select') two other objects in all possible ways. Just two loops:

for (int i = 0; i < 6; ++i) {
    for (int j = i + 1; j < 6; ++j) {
        // here we select all elements except i and j
    }
}

Not very extensible if number of objects grows, but simple enough.

(I'm assuming order doesn't matter: it seems so from your examples)

Answer 2

Permutation is the right place to start. A brute force method would be to find all the six string permutations and just grab the first four and add them to a set. Terribly inefficient, though.

The basic permutation algorithm could be tweaked to generate just groups of four.

Check out this page: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 3

Here is a recursive approach, written in Java, suitable for the general case:

public static void comb(int[] arr, int m) {
    comb(arr, m, 0, new ArrayList<Integer>());
}

public static void comb(int[] arr, int m, int ind, ArrayList<Integer> s) {
    int left = m - s.size();
    if (left == 0) {
        System.out.println(s);
        return;
    }

    if (left > arr.length - ind)
        return;
    comb(arr, m, ind + 1, s);
    s.add(arr[ind]);
    comb(arr, m, ind + 1, s);
    s.remove(s.size()-1);
}

It branches each time it finds an item and needs to decide whether to include it or not. There is also a pruning optimization for avoiding dead ends.