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

Here is a base R method using combn. Lets say you have the integers 1 through 12 and you want to find all of the sets of 5 numbers that sum to 20.

myGroups <- combn(1:12, 5)
mysums <- combn(1:12, 5, FUN=sum, simplify=TRUE)

myAnswers <- myGroups[, mysums == 20]

This returns a matrix where the columns are the sets of numbers:

myAnswers
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    1    1    1    1    1    2
[2,]    2    2    2    2    2    3    3
[3,]    3    3    3    4    4    4    4
[4,]    4    5    6    5    6    5    5
[5,]   10    9    8    8    7    7    6

This will be easy to wrap up in a function. In the function below, x is the input vector, which I set as 1:12 in the example above, and k and n are defined in the OP's question.

myfunction <- function(x, k, n) {
  myGroups <- combn(x, k)
  mysums <- combn(x, k, FUN=sum, simplify=TRUE)

  myGroups[, mysums == n]
}

Note
This method assumes that each entry in x will be used once in the calculation, so on the integers 0:9 that add up to 9 using 4 of them, myfunction returns:

myfunction(0:9, 4, 9)
     [,1] [,2] [,3]
[1,]    0    0    0
[2,]    1    1    2
[3,]    2    3    3
[4,]    6    5    4

Note
If the goal is the allow for repeated use of these integers, we simply must adjust what we feed to myfunction. Note that this will result in duplicated output of sets, since order matters to combn.

---

If repeated integers will be involved, the use of combn has to be modified to return a list so we can use unique to drop duplicate sets:

myfunctionDupes <- function(x, k, n) {
  # return list instead of matrix, with elements sorted
  myGroups <- lapply(combn(x, k, simplify=FALSE), sort)
  # find duplicates
  dupes <- duplicated(myGroups)
  # subset summations to those where myGroups is not a duplicate
  mysums <- combn(x, k, FUN=sum, simplify=TRUE)[!dupes]
  # subset myGroups to the unique values then those with sums == n
  myGroups <- (myGroups[!dupes])[mysums == n]
  # return a matrix
  do.call(cbind, myGroups)
}

This takes a little while to run on @josh-obrien's example, but it produces the same result:

myfunctionDupes(rep(0:9, 4), 4, 9)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18]
[1,]    0    0    0    0    0    0    0    0    0     0     0     0     1     1     1     1     1     2
[2,]    1    1    1    1    0    2    2    0    0     3     0     0     2     2     1     1     1     2
[3,]    2    3    4    1    1    3    2    2    3     3     4     0     3     2     2     3     1     2
[4,]    6    5    4    7    8    4    5    7    6     3     5     9     3     4     5     4     6     3

Answer 2

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