[R] Same sum, different sets of integers
Peter Langfelder
peter.langfelder at gmail.com
Thu Apr 28 04:00:27 CEST 2016
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.
More information about the R-help
mailing list