r - 列出 k 个数字的所有排列，取自 0 :k,，总和为 k

Question

这个问题与另一个问题R:sample()密切相关。 。我想在 R 中找到一种方法来列出 k 个数字的所有排列，总和为 k，其中每个数字都是从 0:k 中选择的。如果k=7，我可以从0,1,...,7中选择7个数字。一个可行解是 0,1,2,3,1,0,0，另一个可行解是 1,1,1,1,1,1,1。我不想生成所有排列，因为如果 k 略大于 7，则会发生爆炸。

当然，在 k=7 示例中我可以使用以下内容:

perms7<-matrix(numeric(7*1716),ncol=7) 
count=0
for(i in 0:7)
    for(j in 0:(7-i))
        for(k in 0:(7-i-j))
            for(l in 0:(7-i-j-k))
                for(n in 0:(7-i-j-k-l))
                    for(m in 0:(7-i-j-k-l-n)){
                            res<-7-i-j-k-l-n-m
                            count<-count+1
                            perms7[count,]<-c(i,j,k,l,n,m,res)
                        }
head(perms7,10)  

但是我怎样才能推广这种方法来解释任何 k 而不必编写 (k-1) 循环呢？我尝试想出一个递归方案:

perms7<-matrix(numeric(7*1716),ncol=7) #store solutions (adjustable size later)
k<-7 #size of interest
d<-0 #depth
count=0 #count of permutations
rec<-function(j,d,a){
    a<-a-j #max loop
    d<-d+1 #depth (posistion)
    for(i in 0:a ) {
        if(d<(k-1)) rec(i,d,a)
        count<<-count+1
        perms7[count,d]<<-i
        perms7[count,k]<<-k-sum(perms7[count,-k])
    }
}
rec(0,0,k)

但是陷入困境，我不太确定这是正确的方法。想知道是否有任何“神奇”的 R 函数可以很好地解决这个(尽管非常具体)问题或只是其中的一部分。

在 k=7 的情况下，所有 2.097.152 排列和总和为 k=7 的 1.716 可以通过以下方式找到:

library(gtools)
k=7
perms <- permutations(k+1, k, 0:k, repeats.allowed=T) #all permutations
perms.k <- perms[rowSums(perms) == k,] #permutations which sums to k

对于 k=8，有 43.046.721 种排列，但我只想列出 6.435 种。非常感谢任何帮助!

Answer 1

有一个包可以解决这个问题...

require( partitions )
parts(7)                                 
#[1,] 7 6 5 5 4 4 4 3 3 3 3 2 2 2 1
#[2,] 0 1 2 1 3 2 1 3 2 2 1 2 2 1 1
#[3,] 0 0 0 1 0 1 1 1 2 1 1 2 1 1 1
#[4,] 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1
#[5,] 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1
#[6,] 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
#[7,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

您似乎正在寻找compositions()。例如对于k=4:

parts(4)

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

compositions(4,4)                                                                          
#[1,] 4 3 2 1 0 3 2 1 0 2 1 0 1 0 0 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 4 0 1 2 3 0 1 2 0 1 0 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 0 1 1 1 1 2 2 2 3 3 4 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 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 4

只是为了检查你的数学......:-)

ncol(compositions(8,8))
#[1] 6435