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

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.

## Answers

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.

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.

If you know k at design time it is easy to generate all the k-combinations using k loops, i.e. if you want all 4-combination, you can do it using 4 loops :

for c1=0 to 1 for c2=0 to 1 for c3=0 to 1 for c4=0 to 1 print c1,c2,c3,c4

If you don't know k at design time, you will need a way to emulate k-loops. This is easy, create an array of size k and store at index i the current value of ci (loop number i index).

c : array[1..k] fill(c,0) // initialize all the cells with 0 do for i=1 to k print c[i] while increment(c) // get next values

increment get the next value and return false if all the values have been used, true otherwise.

increment(c : array[1..k]) begin i=k do c[i]=c[i]+1; if c[i]=2 // i.e. MAX+1 c[i]=0 i=i-1 // incerment previous position else return true // increment done end if while (i>1) // here we need to increment the first position c[i]=c[i]+1 if c[i]=2 // we looped thru all the values c[i]=0 return false end if return true end

This method can be generalized to any loop in any *base* (=different max values for each loop) or with different start values, steps etc ...
This method can also be generalized for generating lexicographical combination with repetition, etc ... google for odometer or take a look at TAOCP Knuth Volume 3 fascicle 2 and 3.

Based on the example you provide, I believe you are referring to k-permutations, not combinations. Cited from Wikipedia:

a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter.

#include<stdio.h> #include<conio.h> void calAns(int idx, int f[3]); int main() { int f[3]; calAns(0,f); getch(); return 0; } void calAns(int idx, int f[3]) { if(idx == 3) { int i; for(i = 0; i<3; i++) printf("%d",f[i]); printf("\n"); return; } f[idx] = 0; calAns(idx+1, f); f[idx] = 1; calAns(idx+1, f); }