用重复生成集合元素的k组合的算法？

Question

我正在寻找一种算法,它将一组两个元素作为输入T = {0, 1},k并生成如下的所有k组合T:

000
001
010
011
100
101
110
111

当它k很小时,可以直接实现迭代,就像k=3上面的例子一样.任何想法如何设计递归算法,使算法独立k.

Answer 1

你可以递归地做.假设这是一种学习练习,我会给你伪代码而不是C程序:

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

前三行是基本案例.pos从零开始,并指示current数组中需要由递归调用的当前级别填充的位置.一旦pos达到N,我们打印当前的组合,并返回到之前的水平.

底部的三行是一个循环,类似于解决问题时的嵌套循环k=3."嵌套"通过递归动态发生:您可以将递归调用的下一级别视为另一级"循环嵌套".从本质上讲,递归解决方案允许您构建N嵌套循环,其中N只在运行时才知道.