Algorithm to partition an integer?

Support, Help & Resources
21

I don’t think I would ever use something like (value, max = value), but nice to know you can do that :slight_smile:

22

Just wanted to write that I will do it this evening, but this seems solved :+1:

Still want to understand how it works, so another task for the evening :wink:

1 Like
23

Fantastic! In SPI, it doesn’t work for values greater than 18. Does SPI invoke some kind of throttling in terms of array size or computing time?

24

What exactly do you mean by “doesn’t work”? Keep in mind that the algorithm’s computation time is (presumably) exponentially increasing with the value.

25

Just completed a run with n=50 in a few seconds (?)
(and 204226 possible partitions)

26

I mean SPI returns (says “All runs completed”), but nothing prints out from the function’s results when the argument is 19 or greater. No value gets returned. 18 and under, a value gets returned and prints out.

27

This is how I used it:

r = integer_sum 50
puts r.length
28

Without hunting through the source code or investigating it a bit more thoroughly, my guess is it is hitting a limit on message size when attempting to send the result to the log window. I could be wrong though :man_shrugging:

29

So you didn’t actually obtain the results, just a count of the results?

30

Well, the result is stored in r and you should not attempt to print it out … :wink:

31

That’s my whole purpose for doing this: to get my hands on those arrays. Is there a way in SPI to redirect the output to a file?

ADDED: Yes, I see when I index the result, I can get a selection of elements of the huge array. But I need the whole enchilada!

32

You can try something like this, splitting the printing over multiple (live) loop iterations:

partitions = integer_sum(50)

live_loop :print do
  puts partitions.tick
  sleep 0.01
end
1 Like
33

Alternatively, use Ruby’s file writing functionality, e.g. like this:

partitions = integer_sum(50)

File.open('path/to/file.txt', 'w') { |file|
  for arr in partitions
    file.write(arr)
    file.write("\n")
  end
}
1 Like
34

0.01 is too short for me on my machine :grimacing: :joy: but it works with a slightly higher value…
A slightly faster alternative could be:

partitions.map do |part|
  in_thread do
    puts part
  end
end

Having said that, using Ruby’s File might indeed be fastest.

35

Yes, Ruby’s File works great.

1 Like
36

Do you mind if I ask what are you trying to do with this algorithm? Just out of curiosity.

I could not resist to play around with similar a idea … and you could possibly do a lot more with less if you use algorithm that simply lists out the even and odd divisors:

define :divisors do |s|
  parts = {:even=>[], :odd=>[], :prime=>[]}
  (1..s).map do |i|
    if s%i==0
      parts[:even].push(s/i)
    else
      if ((2..Math.sqrt(i)).none? { |n| (i % n).zero? })
        # If odd and prime - gotta avoid those
        parts[:prime].push(i)
      else
        parts[:odd].push(i)
      end
    end
  end
  parts
end

print divisors 20

Edit: Also added list of primes. Gotta avoid those if you want to reduce your stuff nicely.

Depending on what you are actually trying to do of course :slight_smile:

37

I’m programming the sequencer I’ve been working on, ELLIOTT, to do various things with melodies in any division of the octave, that is, any tuning. Representing a melody as a series of intervals, the ability to access all octave-sized rising melodic lines will be a big help to do those various things. An integer partition is identical to an octave-sized rising melodic line. You might call a partition a scale, but intervals of all sizes are possible, so the idea of a scale is unnatural here. For example, I can also use these integer partitions to do things with chords.

38

Sounds interesting. Is it up somewhere?

39

No, I’m still working on it. Maybe a demo in the next few weeks.

2 Likes
40

Interesting use case for this algorithm for sure. Very cool!

I’m not sure if what I have built will solve for this, but if you are randomly selecting one of the possible sets of integers in your algorithm you may be able to optimize the approach by selecting random integers within the available space left over.

For example, if you are want a random set of integers that add up to 18, you could repeat the process of selecting a random number between 1 and how much “space” is left - repeating this process until you’ve filled up 18.

define :random_integer_sum do |number|
  
  # Empty result for the return
  result = []
  
  # While we have numbers left
  while number > 0
    chosenInt = rrand_i(1,number)
    result.push chosenInt
    number -= chosenInt
  end
  
  # Return the resultant array of ints
  return result
  
end #end function

# Run the function
puts random_integer_sum(5)
puts random_integer_sum(10)

I do a similar approach in my algorithm where I randomly generate melodies and rhythms but ensure they are “bound” by some time signature or interval of time.