stressed_geek - 1 month ago 5x
C Question

# 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`
.

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.