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);
}

Need Your Help

Zend Framework rememberMe() doesnt seem to remember me

zend-framework authentication session remember-me

My session seems to only be valid in the current window/tab. Also it seems to timeout quickly. Heres how I'm currently attempting to do it:

Does anyone have a description of the return codes from libusb on Mac OS X?

macos usb

I am trying to debug a libusb-based driver that work just fine on Linux and Windows, but fail on Mac OS X. However I am unable to find a description of the return codes from libusb.