可以在N个插槽中排列K个项目的所有可能方式

Question

我正在寻找一个算法，以找到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个组合。

Answer 1

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

一般情况下的解决方案显然是采用N - 1的解决方案，然后依次将集合的每个元素作为结果的前缀。在伪代码中：

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

这可以在Java语言中以递归方式实现，但是对于中等大的n值，您会遇到堆栈溢出错误；我还怀疑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中，然后依次迭代选项，以获得将它们添加到先前结果的结果。

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

Answer 2

我将使用基数k中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时，操作终止。

如果你尝试过但不能做到这一点，请用评论告诉它。