算法生成组具有重复元素的K-组合？ [英] Algorithm to generate k-combinations of elements of set with repetition?

问题描述

我在寻找一种算法，需要输入一个集中的两个元素 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.

这篇关于算法生成组具有重复元素的K-组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！