Skip to content

Same sum, different sets of integers

5 messages · Atte Tenkanen, Jim Lemon, jim holtman +1 more

Atte Tenkanen
# 
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
# 
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:
jim holtman
# 
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.
+             t(apply(add2N, 1, sort))  # sort
+             , 1
+             , toString
+             )
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:

            

      
      
      
    

        

      
      
    

        

  
  


  


      

    

    

      
      

        


  

        

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

            

      
      
      
    

        
[[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:

            

      
      
      
    

        

      
      
    

            

      
      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Atte Tenkanen
    

    

      
      #
    

  


  

      
Thanks for the suggestions, all of you!
I first began to think about using somehow permutations of the 
gtools-package. I will continue utilizing Peter's solution.

My purpose is to divide basic musical rhythm units (whole note, half 
note, quarter note etc durations) to meaningful entities in algorithmic 
composition. I use R for that. Usually, there are - in the composition 
algorithm - random number generators, which "composes" different 
versions of music. Those RNG's (sample in R) can be - for their part - 
conducted by using different constraints and probabilities. Here I draw 
rhythms.

For example, if my quarter note (1/4) is 1024 ticks in MIDI format, I 
may like to split it into quintuples, ie. five units, using ties 
differently:

1024*c(1/5, 4/5), 1024*c(2/5, 3/5),... This way I can produce and output 
rich and still usable rhythms to music notation software, keep the 
rhythmic entities playable and readable over barlines.

Yours,

Atte

28.4.2016, 5.00, Peter Langfelder kirjoitti: