我在寻找一种算法,需要输入一个集中的两个元素 T = {0,1}
和 K
和生成所有 K
T的-combinations
如下:
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
这是直接实现迭代时, K
小,就像 K = 3
在上面的例子。任何想法如何设计一个递归算法,这样的算法是独立 K
。
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
.
您可以递归地做到这一点。假设这是各种各样的学习锻炼,我会给你假code,而不是一个C程序:
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
前三名线是一个基本情况。 POS
从零开始,并指示电流
阵列需要通过的电流水平填充的位置递归调用。一旦 POS
达到 N
,我们打印出当前组合,并返回到之前的水平。
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.
的底部的三行是一个循环,在一个解决问题的办法类似嵌套的循环时 k = 3的
。而筑巢动态情况,通过递归:你能想到递归调用为循环嵌套的另一个层面的下一级。从本质上讲,递归解决方案可以让您建立 N
嵌套循环,其中 N
仅在运行时知道。
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.
下一篇:哥伦布的序列哥伦布、序列