文章/答案/技术大牛

发布

社区首页 >问答首页 >列出所有k数的排列，取自0:k，之和为k

问列出所有k数的排列，取自0:k，之和为k
EN

Stack Overflow用户

提问于 2014-09-25 09:00:57

回答 1查看 169关注 0票数 2

这个问题与另一个问题R:sample()密切相关。我想在R中找到一种方法，列出k个数的所有排列，之和为k，其中每个数从0:k中选择。如果是k=7，我可以从0,1，1，1，...,7中选择7个数字。一个可行的解决方案是，0，1，2，3，1，0，另一个是1,1,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-1)循环的情况下解释任何k呢？我试图想出一个递归方案：

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。任何帮助都是非常感谢的！

recursion

permutation

loops

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-09-25 10:34:34

有个包裹.

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

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/26034476

复制

相似问题

问列出所有k数的排列，取自0:k，之和为k
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问列出所有k数的排列，取自0:k，之和为kEN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问列出所有k数的排列，取自0:k，之和为k
EN