Large Partition Calculation Problem

I am attempting to calculate the ways to partition 121 into integer partitions i.e. integer partition of 5 are

5

4+1

3+1+1

2+1+1+1

1+1+1+1+1

3+2

but there are 2056148051 ways to do it. But i wanted to actually find the ways it is done, but it always crashes my memory. I don't care how

I used http://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer this file which allows you to calculate it with partition(n) which works fine for n<70 but my computer can't handle more. I have a big external harddrive,12Gb of Ram, and am willing to take more computation time but i don't know how to do this task. Any help in calculating this would be appreciated.

Answer 1

[John D'Errico]

I checked, and you are correct. There are roughly 2 billion ways to partition the integer 121. Given that is my tool you reference to calculate those partitions, I guess I'm a good person to answer.

numberOfPartitions(121)
ans =
    2056148051

This is a big number. How much RAM will it take to store the solution? Remember that since matrices in MATLAB are rectangular, partitions will return an array of size 2056148051 by 121, that indicates the number of occurrences for each integer 1:121 in the respective sum.

format short eng
2056148051*121*8
ans =
     1.9904e+012

So the array will require roughly 2 terabytes of RAM to store, far more than you have available.

I suppose I could have used sparse storage for this array, but the sparse matrix would have been quite a bit more difficult to create, taking much more time for the code to work.

A more efficient choice could have been to create the resulting matrix as uint8. That would have taken only one byte per element to store, instead of using double precision, so 8 bytes per element. But even a uint8 array would have needed roughly 250 GB of RAM to store.

2056148051*121
ans =
   248.7939e+009

It would be fairly easy to modify partitions to return a uint8 result when that is possible, although I am not sure that UINT8 computations were available to me when I wrote partitions (it was a while ago), so that was possibly not an option then. And at that time, a 250 GB array would have been impossible to even consider. Even now, that is still far to big for my system to handle.

[Jeff Lutton]

Thank you for your reply. It is a really good and easy to use system that i have worked with before and never had a problem. Has there been any improvement in ways to calculate since you wrote it, or is wanting to be able to calculate this just too large to reasonably do?

[John D'Errico]

Partitions uses a recursive solution, which in my opinion is still the best way to do this computation.

As I said, it would be eminently possible to modify partitions to always return a uint8 array. That would take only one byte per element to store, instead of 8, so an 87.5% savings in memory. Here it would still be inadequate though, in terms of how partitions returns the result. As long as no element is larger than 255, that would work.

However, it would be problematic, since suppose someone wanted to compute the ways to represent the integer as large as 256, as sums of the integers [1 5 10 25 50 100]? That would generate an array of size 6620 by 6, with at least one element that exceeds 255. So uint8 would fail there.

Or, partitions could generate cell arrays that contain the solutions in a different form, or use sparse storage. But those forms would be seriously slower to run. So your problem might still be unmanageable, now because of time. (I'd need to look at the cell array idea. It might be possible to get as high as partitions(100) that way. But 121 would probably still be a bit too far.) I'll take a look at it.