如何找到所有可能的k整数，它们的和等于R中的某个数字 [英] How to find all the possible k integers which sum of them equals to a certain number in R

问题描述

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

suppose I have a integer n and k, I need find all the possible combinations of k integers which sum to n. I was wondering to how do I implement this efficiently.

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

right now, what I am doing is super slow, I created kth cartesian product of a sequence from 1 to n. And then loop over all the possible combinations to check if it satisfy the sum.Below is my code.

首先获得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是整数

v is the sequence from 1 to n and k is the integer

然后循环播放

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,])
  }
}

这太慢了，我想知道有没有更快的方法来实现呢?

this is super slow and I was wondering is there any faster way to implement this?

推荐答案

根据注释中的问题澄清进行

听起来像是您想要所有合成，而不是整数n的所有分区. (只有两个序列的术语顺序不同，它们被认为是相同的分区，但具有不同的组成.)

Sounds like you are wanting all compositions, rather than all partitions of the integer n. (Two sequences differing only in the order of their terms are considered to be the same partition, but different compositions.)

要获取合成，请使用 partitions 包中的compositions()函数:

To get compositions, use the compositions() function from the partitions package:

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

---

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

如果我正确理解了您的问题，则可以使用 partitions 软件包中的restrictedparts().

If I correctly understand your question, you could use restrictedparts() from the partitions package.

例如:

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的倒数第二行中的一个小错误，当给定的限制仅允许一个分区时，它可能会引发错误.我已经向软件包作者发送了一个建议的修复程序，但是与此同时，您可以通过设置函数参数decreasing=FALSE:

Due to a minor bug in the second to last line of restrictedparts, it can throw an error when the given restriction allows just one partition. I've sent a proposed fix to the package author, but in the meantime you can get around this by setting the function argument 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

这篇关于如何找到所有可能的k整数，它们的和等于R中的某个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！