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.

Confection

This is permutation, in combinations order does not matter. – Monotint

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.

Nonproductive

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.

Hellenhellene

Answer 3

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.

Extraditable

Answer 4

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.

Hydrograph

This should probably be a comment, not an answer. – Rumania

Answer 5

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

Nomenclator

Your answer certainly is worth a little explanation. Kindly refer to stackoverflow.com/help/how-to-answer . – Cudweed

Answer 6

Thanks to @Sergey Kalinichenko, I've made a little recursive app. Even though this is Java code, I hope it would help someone.

Key method is generateCombinationsRecursively.

Test class:

public class CombinationOKTest {

    CombinationOK combinationOK;

    @BeforeEach
    void setUp() {
        combinationOK = new CombinationOK();
    }

    @Test
    void allCombinationsWithTwoElementsAndLengthThreeBinary() {
        List<Integer> elementList = List.of(0, 1);
        int combinationLength = 3;

        List<List<Integer>> combinationList =
                combinationOK.getAllCombinations(elementList, combinationLength);

        assertEquals(8, combinationList.size());
        assertEquals(List.of(
                        List.of(0, 0, 0),
                        List.of(0, 0, 1),
                        List.of(0, 1, 0),
                        List.of(0, 1, 1),
                        List.of(1, 0, 0),
                        List.of(1, 0, 1),
                        List.of(1, 1, 0),
                        List.of(1, 1, 1)),
                combinationList);
    }
}

Implementation class:

public class CombinationOK {
    public List<List<Integer>> getAllCombinations(List<Integer> elementList,
                                                  int combinationLength) {
        List<List<Integer>> combinationList = new ArrayList<>();
        Integer[] combination = new Integer[combinationLength];

        generateCombinationsRecursively(elementList, combinationList, combination, 0);

        System.out.println();
        System.out.println(combinationList);
        return combinationList;
    }

public class CombinationOK {
    public List<List<Integer>> getAllCombinations(List<Integer> elementList,
                                                  int combinationLength) {
        List<List<Integer>> combinationList = new ArrayList<>();
        Integer[] combination = new Integer[combinationLength];

        generateCombinationsRecursively(elementList, combinationList, combination, 0);

        System.out.println();
        System.out.println(combinationList);
        return combinationList;
    }

/**
 *
 * Magic is done in this recursive method <code>generateCombinationsRecursively</code>.
 *
 * @param elementList elements that combinations are made of (T)
 * @param combinationList is resulting list of combinations as a result of recursive method
 * @param combination is array of elements, single combination with variable length (k)
 * @param position of one element from the list <code>elementList</code> in the <code>combination</code> array
 *
 */
private void generateCombinationsRecursively(List<Integer> elementList,
                                             List<List<Integer>> combinationList,
                                             Integer[] combination,
                                             int position) {
    if (position == combination.length) {
        System.out.println(Arrays.asList(combination));
        combinationList.add(new ArrayList<>(Arrays.asList(combination)));
        return;
    }

    for (int i = 0; i < elementList.size(); i++) {
        combination[position] = elementList.get(i);
        generateCombinationsRecursively(
                elementList, combinationList, combination, position + 1);
    }
}

}

Summary:

Main functionality is in this recursive method generateCombinationsRecursively.

Parameter position is variable, depending on how deep recursive function goes. Max value for position parameter is the combination's list size (k). If the max value (k) is reached (first block of the method generateCombinationsRecursively), new combination is added to the resulting combinationList list and recursion finishes.

Second block of the method generateCombinationsRecursively is the for loop which iterates throughout all elements in the list elementList. Depending on position value, combination list is populated with element from elementList (T). Next, the recursive method generateCombinationsRecursively is called with accent on the position argument, which is incremented so it points to the next position in the combination, that recursive method will populate with the next element (from T).

Output combinations:

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

Output resulting combinationList list:

[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Aminaamine