thr3ads.net - R help - [R] Same sum, different sets of integers [Apr 2016]

If this information is useful, please help other people find it:
Share via:

Atte Tenkanen

2016-Apr-27 15:46 UTC

[R] Same sum, different sets of integers

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

Jim Lemon

2016-Apr-28 00:21 UTC

head link

[R] Same sum, different sets of integers

Hi Atte,
I'm not sure that this actually works, and it's very much a quick hack:

sums_x<-function(x,addends=1,depth=1) {
 if(depth==1) {
  addends<-rep(addends,x)
  addlist<-list(addends)
 } else {
  addlist<-list()
 }
 lenadd<-length(addends)
 while(lenadd > 2) {
  addends<-c(addends[depth]+1,addends[-c(depth,depth+1)])
  lenadd<-lenadd-1
  if(sum(addends) == x) addlist[[length(addlist)+1]]<-addends
  cat(depth,"-",addends,"\n")
  if(lenadd > 2 && depth+1 < lenadd)
   addlist<-c(addlist,(sums_x(x,addends=addends,depth=depth+1)))
 }
 return(addlist)
}

This doesn't return all the permutations of the addends, but it's all
the time I have to waste this morning.

Jim

On Thu, Apr 28, 2016 at 1: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.

jim holtman

2016-Apr-28 01:10 UTC

head link

[R] Same sum, different sets of integers

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]]

Peter Langfelder

2016-Apr-28 02:00 UTC

head link

[R] Same sum, different sets of integers

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.

Possibly Parallel Threads

Search for more apparently analagous threads

R help - Apr 2016 - Same sum, different sets of integers

[R] Same sum, different sets of integers

[R] Same sum, different sets of integers

[R] Same sum, different sets of integers

[R] Same sum, different sets of integers

Possibly Parallel Threads