如何找到所有可能的k整数，它们的和等于R中的某个数字

一尘不染

如何找到所有可能的k整数，它们的和等于R中的某个数字

algorithm

假设我有一个整n和k，我需要找出所有可能的组合k整数其总和n。我想知道如何有效地实现这一目标。

现在，我的工作非常慢，我创建kth了从1到n的序列的笛卡尔积。然后遍历所有可能的组合以检查是否满足总和。以下是我的代码。

首先获得k笛卡尔积

cart = function(v,k){
  x = v
  f = v
  for(i in 1:(k-1)){
    f = merge(f,x,all=T)
    f = as.matrix(f)
    colnames(f) = NULL
  }
  return(f)
}

v是从1到n的序列，k是整数

然后循环

combine = cart(v=seq(1,n),k=k)
sum = 0
for(i in 1:dim(combine)[1]){
  if(sum(combine[i,])==n){
    sum = sum + sum(combine[i,])
  }
}

这是超级慢，我想知道是否有更快的方法来实现这一目标？

阅读 213

2020-07-28

共1个答案

一尘不染

根据对评论中问题的澄清进行编辑：

听起来您需要所有组成，而不是integer的所有分区n。（两个仅在术语顺序上不同的序列被视为相同的分区，但组成不同。）

要获取组成，请使用 partitions* 包中的compositions()函数： *

library(partitions)
compositions(4, 3, include.zero=FALSE)
#           
# [1,] 2 1 1
# [2,] 1 2 1
# [3,] 1 1 2

原始答案，留在原处，直到软件包作者有机会看到为止：

如果我正确理解您的问题，则可以restrictedparts()从 partitions 包中使用。

例如：

library(partitions)

restrictedparts(9,4)
#                                         
# [1,] 9 8 7 6 5 7 6 5 4 5 4 3 6 5 4 4 3 3
# [2,] 0 1 2 3 4 1 2 3 4 2 3 3 1 2 3 2 3 2
# [3,] 0 0 0 0 0 1 1 1 1 2 2 3 1 1 1 2 2 2
# [4,] 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2

## Or, for partitions employing only non-zero integers
restrictedparts(9,4,include.zero=FALSE)
#                 
# [1,] 6 5 4 4 3 3
# [2,] 1 2 3 2 3 2
# [3,] 1 1 1 2 2 2
# [4,] 1 1 1 1 1 2

由于的倒数第二行中有一个小错误，restrictedparts当给定的限制仅允许一个分区时，它可能会引发错误。我已经向软件包作者发送了建议的修复程序，但是与此同时，您可以通过设置function参数来解决此问题decreasing=FALSE：

## Throws an error
restrictedparts(4,3,include.zero=FALSE)
# Error in class(x) <- "matrix" : 
# invalid to set the class to matrix unless the dimension attribute is of # length 2 (was 0)

## Works just fine
restrictedparts(4,3,include.zero=FALSE,decreasing=FALSE)
#       
# [1,] 1
# [2,] 1
# [3,] 2

2020-07-28