algorithm - How to find all the possible k integers which sum of them equals to a certain number in R

Question

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.

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.

first get k cartesian product

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 is the sequence from 1 to n and k is the integer

then loop over

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?

Answer 1

Edited based on clarification of question in comments:

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.)

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

---

Original answer, left in place until the package author has had a chance to see it:

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

For example:

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

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