[R] Same sum, different sets of integers

[Peter Langfelder]

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));
}

> sumsToN(4)
[[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

> sumsToN(5)
[[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
>>
>> ______________________________________________
>> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>>
>
>         [[alternative HTML version deleted]]
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.