Algorithm to generate k-combinations of elements of set with repetition?

Question

I am looking for an algorithm which takes as input a set of two elements T = {0, 1} and k and generates all k-combinations of T as follows:

000
001
010
011
100
101
110
111

It is straightforward to implement iteratively when k is small, like k=3 in the above example. Any ideas how to design a recursive algorithm so that algorithm is independent of k.

Answer 1

You can do it recursively. Assuming that this is a learning exercise of sorts, I would give you pseudocode instead of a C program:

generate (int pos, int element[T], int current[N])
    if pos == N
        print (current)
        return

    for i : 0..T
        current[pos] = element[i]
        generate(pos+1, element, current)

end

The top three lines are a base case. pos starts at zero, and indicates the position in the current array that needs to be filled by the current level of the recursive invocation. Once pos reaches N, we print the current combination and return to the prior level.

The bottom three lines are a loop, similar to the nested loops in a solution to the problem when k=3. The "nesting" happens dynamically through recursion: you can think of the next level of the recursive invocation as another level of "loop nesting". Essentially, the recursive solution lets you build N nested loops, where N is known only at run-time.

Answer 2

You dont need a recursive algorithm. If you look at your list, you should see the "pattern".

That are the binary numbers from 0 to 2^k-1. So the easy solution is just to count.

for (i = 0; i < (1<<k); i++) {
    // generate the binary representation of i
    for (c = k-1 ; c >= 0; c--) {
       r = i >> c;
       printf((r & 1) ? "1" : "0");
    }
    printf("\n");
}

EDIT: In case you need a recursive apporach, you can easily do it by recurse over the length, I give some pseudocode (because in my eyes recursion makes only sense when it is some assignement/homework, and then you should do something yourself):

print_all_combos(int k, char* prefix) {
   if (k == 0) {
      printf("%s\n", prefix);
      return;
   }
   append(prefix, "0");
   print_all_combos(k - 1 , prefix);
   remove_last_char(prefix);
   append(prefix, "1");
   remove_last_char(k - 1, prefix);
}

and call it with k and an empty string as parameter.