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

我正在寻找一种算法来查找K个项目的所有K个组合。所有可能的方式，其中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个的组合。

来源

2012-07-06 Vivek

这是**的变体**，因为顺序是相关的。您的问题与N位数字的K数字一一对应。 – 2012-07-06 11:00:30

我同意@MarkoTopolnik。但是，这几乎是一个常见问题，所以我投票结束。 – 2012-07-06 11:07:02

[重复变异的代码（combinatorics）的可能的重复？]（http://stackoverflow.com/questions/2366074/code-for-variations-with-repetition-combinatorics） – 2012-07-06 11:07:59

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

通常情况下的解决方案是通过采用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，然后（我希望！）只是依次迭代选项，以获得将结果添加到前一结果的结果。

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

来源

2012-07-06 11:09:47

我将使用基数为k的N位计数器。例如：K = 3，N = 5

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

实现这样的计数器是容易的，只要保持大小为n + 1，将所有元素的数组tozero起初，每次增加最新元件，并且如果它会超过k-1，增加下一个邻居（直到邻居超过k-1）。当n + 1元素设置为1时动作终止。

如果您尝试过并且无法做到这一点，请通过评论告诉它。

来源

2012-07-06 11:20:27

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

回答

相关问题