I came up with this, using recursion. Short and should work for n
greater than 9 :)
Peter
sumsToN = function(n)
{
if (n==1) return(1);
out = lapply(1:(n-1), function(i) {
s1 = sumsToN(n-i);
lapply(s1, c, i)
})
c(n, unlist(out, recursive = FALSE));
}
[[1]]
[1] 4
[[2]]
[1] 3 1
[[3]]
[1] 2 1 1
[[4]]
[1] 1 1 1 1
[[5]]
[1] 1 2 1
[[6]]
[1] 2 2
[[7]]
[1] 1 1 2
[[8]]
[1] 1 3
[[1]]
[1] 5
[[2]]
[1] 4 1
[[3]]
[1] 3 1 1
[[4]]
[1] 2 1 1 1
[[5]]
[1] 1 1 1 1 1
[[6]]
[1] 1 2 1 1
[[7]]
[1] 2 2 1
[[8]]
[1] 1 1 2 1
[[9]]
[1] 1 3 1
[[10]]
[1] 3 2
[[11]]
[1] 2 1 2
[[12]]
[1] 1 1 1 2
[[13]]
[1] 1 2 2
[[14]]
[1] 2 3
[[15]]
[1] 1 1 3
[[16]]
[1] 1 4
On Wed, Apr 27, 2016 at 6:10 PM, jim holtman <jholtman at gmail.com> wrote:
This is not the most efficient, but gets the idea across. This is the
largest sum I can compute on my laptop with 16GB of memory. If I try to
set N to 9, I run out of memory due to the size of the expand.grid.
N <- 8 # value to add up to
# create expand.grid for all combinations and convert to matrix
x <- as.matrix(expand.grid(rep(list(0:(N - 1)), N)))
# generate rowSums and determine which rows add to N
z <- rowSums(x)
# now extract those rows, sort and convert to strings to remove dups
add2N <- x[z == N, ]
strings <- apply(
+ t(apply(add2N, 1, sort)) # sort
+ , 1
+ , toString
+ )
# remove dups
strings <- strings[!duplicated(strings)]
# remove leading zeros
strings <- gsub("0, ", "", strings)
# print out
cat(strings, sep = '\n')
1, 7
2, 6
3, 5
4, 4
1, 1, 6
1, 2, 5
1, 3, 4
2, 2, 4
2, 3, 3
1, 1, 1, 5
1, 1, 2, 4
1, 1, 3, 3
1, 2, 2, 3
2, 2, 2, 2
1, 1, 1, 1, 4
1, 1, 1, 2, 3
1, 1, 2, 2, 2
1, 1, 1, 1, 1, 3
1, 1, 1, 1, 2, 2
1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 1, 1
Jim Holtman
Data Munger Guru
What is the problem that you are trying to solve?
Tell me what you want to do, not how you want to do it.
On Wed, Apr 27, 2016 at 11:46 AM, Atte Tenkanen <attenka at utu.fi> wrote:
Hi,
Do you have ideas, how to find all those different combinations of
integers (>0) that produce as a sum, a certain integer.
i.e.: if that sum is
3, the possibilities are c(1,1,1), c(1,2), c(2,1)
4, the possibilities are
c(1,1,1,1),c(1,1,2),c(1,2,1),c(2,1,1),c(2,2),c(1,3),c(3,1)
etc.
Best regards,
Atte Tenkanen