Algorithm to partition an integer?

Support, Help & Resources
1

I’d like to find an algorithm that, given an integer n, will return the set of arrays of positive integers that sum to n. I’ve looked around the web, and the most promising thing I could find in Runy was here. That code is:

s=0
l=[[n=gets.to_i,n]]
(a,i=l.pop;a>0&&i>0&&l+=[[a-i,i],[a,i-1]];a==0&&s+=1)until l==[]
  print s

and I must say, I have no idea what’s going on there. More importantly, it throws an error about opening a file, so my non-understanding of syntax outside of SPI makes this a problem for me. Is there a simple fix here?

2

The error is due to gets in the second line. It tries to get some user input, which is not possible as SP has no console to be used for that.

Not 100% sure, but you should probably replace the second line by:

l = [[<n>]]

Where <n> needs to be replaced by the number you want as sum.

1 Like
3

To clarify your original intent: do you want all possible partitionings, or a specific one? If the latter, what are your criteria?

4

I’d like to get all possible partitionings, as an array of arrays.

Now I do:

s=0
n=12
l = [[n]]
(a,i=l.pop;a>0&&i>0&&l+=[[a-i,i],[a,i-1]];a==0&&s+=1)until l==[]
  print s

but I get the error

undefined method '>' for nil:NilClass

Pardon my ignorance, but I can’t tell what ‘>’ does in this context.

ADDED: I guess that ‘>’ is simply the greater than sign, but SPI throws an error when using greater than with an array. Is there some substitute in this code for a > 0?

I also can’t figure out exactly how the syntax a,i = l.pop works.

5

Sorry, line 2 needs to be like

l=[[n=5,n]]

(with 5 being your example desired sum).

But still, the code does not do what you want. It prints 7 with 5 as input. Not so familiar with Ruby, and a bit short in time to explore what exactly is happening in the until loop. I’ll try to post a (more readible) algorithm here later.

1 Like
6

That expression uses what ruby calls ‘parallel assignment’ - it is a way of assigning to multiple variables in a single expression. In the original code where we have:

l=[[n=gets.to_i,n]]

and later:

a,i=l.pop;

The latter takes the next element (which is [n=gets.to_i,n]) from the array l, and assigns the values of elements 0 and 1 of the array to a and i respectively.

1 Like
7

So then i is sometimes nil and not an array?

8

Reading your original source, it turns out that the algorithm is not what you want. It only calculates the number of possible partitionings, not the actual partitionings.

9

Not sure - i is assigned the value of n by that original code, that’s all I know.

10

I would think that after you pop a 1-element array, the next pop gives you nil.

I guess this is a request for an algorithm to partition an integer. I found one that will partition an integer using a set of allowable values, but it only uses an allowable at most one time.

11

I don’t either and would not bother to find out :sweat_smile:

You could use array combination with range to find all that match the integer, like:

define :integer_sum do |int|
  (1..9).to_a.combination(2).find_all { |x, y| x + y == int }
end

print integer_sum(8)
12

Ah yes, but that’s where the until l == [] comes in :slightly_smiling_face:

13

I thought an empty array is still an array. I was getting nil so that l.class gave me NilClass.

14

Is that only going to work for pairs? For example, one partition of 8 is {1, 1, 1, 1, 1, 1, 1, 1}.

15

Ah, yes. You are right.

16

Here is a nice explanation how to implement such an algorithm, including implementations in different languages:

There is no Ruby implementation, but doing it from the description, or translating the Python version, should be straight-forward. I can do that later today if you feel it exceeds your Ruby/Python skills.

1 Like
17

That could well be because if a parallel assignment contains more variables on the left hand side than values to assign to them on the right hand side, the excess variables are set to nil. (Such as where you had l = [[n]] and then a,i=l.pop;)

(Although did you mean i was nil, not l?)

18

There’s no question it exceeds my Ruby/Python skills. I mean, I expect I could eventually figure it out, but I’d spend an inordinate amount of time on what amounts to a one-off for someone who only uses SPI in routine ways. If you’re able to spoonfeed me this without too much trouble, I’d greatly appreciate it. I think a lot of other people would, too, because I see solutions online in other programming languages, just not for Ruby, so I expect you’d also be greatly appreciated at GeeksforGeeks, StackOverflow, etc.

19

I found one from stackexchange that is almost comprehensible :slight_smile:

So not my code but seems to work:

define :integer_sum do |value, max = value|
  if value == 0
    [[]]
  else
    1.upto(max).flat_map do |n|
      integer_sum(value - n, [value, n].min).map do |ns|
        [n] + ns
      end
    end
  end
end

print integer_sum 8
2 Likes
20

Nice recursive function :+1: