生成M个仓中N个球的所有排列 [英] Generating all permutations of N balls in M bins

问题描述

我想在m箱中生成一组n球的排列.以下一组嵌套列表会生成这些排列.

I want to generate a set of permutations of n balls in m bins. The following set of nested lists generates those permutations.

n <- 3
m <- 4
v <- rep(0,m)
for (i in n:0){
  for (j in (n-sum(i)):0){
    for (k in (n-sum(i,j)):0){
      for (l in (n - sum(i,j,k)):0){
        v <- c(i,j,k,l)
        print(v)
        if (sum(v) == n){ break }
      }
    }
  }
}

哪个打印解决方案:

[1] 3 0 0 0
[1] 2 1 0 0
[1] 2 0 1 0
[1] 2 0 0 1
[1] 1 2 0 0
[1] 1 1 1 0
[1] 1 1 0 1
[1] 1 0 2 0
[1] 1 0 1 1
[1] 1 0 0 2
[1] 0 3 0 0
[1] 0 2 1 0
[1] 0 2 0 1
[1] 0 1 2 0
[1] 0 1 1 1
[1] 0 1 0 2
[1] 0 0 3 0
[1] 0 0 2 1
[1] 0 0 1 2
[1] 0 0 0 3

排列的总数将为choose(n+m-1,m-1)，排列的顺序对我而言无关紧要.但是我很难把它变成一个可以占用任意数量的bin的函数. (尽管我的尝试不会很好地破坏它，但是它只是嵌套循环的混杂.)因此，如果比我更精明的人可以将上面的嵌套循环转换为一个函数，我将不胜感激.

The total number of permutations will be choose(n+m-1,m-1), and the order of the permutations does not matter to me. But I am having a hard time making this into a function that can take an arbitrary number of bins. (I won't spoil the well with my attempts, it is just jumble of nested loops though.) So if someone more saavy than me could translate the nested loops above into a function I would appreciate it.

或者如果已经有一种功能可以进行这种类型的排列(或者可以采用其他算法)，我将不胜感激.我希望使用一种方法，该方法不会生成多余的排列(此处的那些加起来不等于n)，然后将其丢弃，但是对于像这样的小问题，使用可以做到这一点的解决方案即可.

Or if there is already a function available to conduct this type of permutation (or a different algorithm to follow) I would appreciate being told about it. I would prefer an approach that does not generate superfluous permutations (here ones that do not add up to n) and then discards them, but for small problems like this a solution that does that would be acceptable.

推荐答案

library(partitions)
compositions(3,4)

# [1,] 3 2 1 0 2 1 0 1 0 0 2 1 0 1 0 0 1 0 0 0
# [2,] 0 1 2 3 0 1 2 0 1 0 0 1 2 0 1 0 0 1 0 0
# [3,] 0 0 0 0 1 1 1 2 2 3 0 0 0 1 1 2 0 0 1 0
# [4,] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 3

这篇关于生成M个仓中N个球的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！