stressed_geek - 1 year ago 47

C Question

I am looking for an algorithm which takes as input a set of two elements

`T = {0, 1}`

`k`

`k`

`T`

`000`

001

010

011

100

101

110

111

It is straightforward to implement iteratively when

`k`

`k=3`

`k`

Answer Source

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.