1

我正在寻找一种算法来查找 K 值到 n 项的所有组合。

例子：

K 值为 [R,B] & N 为 2 所以我得到 {RR, RB, BR, BB} 2*2 = 4 种方式

K 值为 [R,B] & N 为 3 所以我得到 {RRR, RRB, RBB, RBR, BRR, BRB, BBR, BBB} 2*2*2 = 8 种方式

我需要找出通用算法，以找到可以将 K 项排列在 N 个插槽中的所有可能方式。（允许重复）

另一个例子是：

K 值为 [R,G,B] & N 为 5，所以我需要找到 3^5 = 81 种组合。

4

2 回答 2

2

这个问题非常适合递归解决方案。

一般情况下的解决方案显然是通过获取 的解决方案N - 1，然后将每个集合的元素依次添加到结果中来形成的。在伪代码中：

f(options, 0) = []
f(options, n) = options foreach o => o ++ f(options, n-1)

n这可以在 Java 中递归实现，但是对于中等大的;值，您会遇到堆栈溢出错误。而且我还怀疑 JIT 编译器在优化递归算法方面效率较低，因此性能会受到影响。

但是，递归算法总是可以转换为等效的循环。在这种情况下，它可能看起来像：

List<String> results = new ArrayList<String>();
results.add(""); // Seed it for the base case n=0
for (int i = 0; i < n; i ++) {
    List<String> previousResults = results;
    results = new ArrayList<String>();
    for (String s : options) {
       for (String base : previousResults) {
           results.add(s + base);
       }
    }
}
return results;

这工作（我希望！）类似于递归方法 - 在每次迭代中，它将当前进度（即 的结果n-1）“保存”到previousResults，然后依次迭代选项，以获得将它们添加到前一个的结果结果。

看看通过任何自动递归到迭代算法传递递归解决方案的效果，并将可读性和性能与这个手工创建的算法进行比较，将会很有趣。这留给读者作为练习。

于 2012-07-06T11:09:47.667 回答
1

我将在基础桶中使用 N 位计数器：k=3, n=5

(0,0,0,0,0)
(0,0,0,0,1),
....
(2,2,2,2,2)

实现这样一个计数器很简单，只需保持大小为 n+1 的数组，首先将所有元素设置为零，每次增加最新元素，如果从 k-1 开始超过，则增加下一个邻居（直到邻居超过 k-1 ）。当 n+1 个元素设置为 1 时，动作终止。

如果您尝试过但不能这样做，请用评论告诉它。

于 2012-07-06T11:20:27.963 回答