File Exchange

image thumbnail

Integer partition generator

version 1.11.0.0 (5.44 KB) by David Holdaway
Generates a table of all integer partitions of integers from 0 to N.

6 Downloads

Updated 11 Jun 2012

View License

Integer partitions are the different ways to express an integer say "4" as a sum of other positive integers, in this case we would have 4=4,3+1,2+2,2+1+1,1+1+1+1. This program calculates all the partitions of every integer up to N which it stores in a cell array.

There is the option of only using partitions with up to "maxnum" integers, e.g. if maxnum = 3 the parition 1+1+1+1 (of 4) would be disallowed.

Also contained is a file to generate the number of integer partitions of an integer N using up to k integers which is used in the main file. Both files work via the recursive property of integer partitions and use integer class variables.

Update: Version two also allows the extra option of using only a restricted range of integers for the partition as well as a restricted number.

Example Useage:

Say I wanted to generate all the partitions of the numbers 0-100, using at most 6 numbers. Of which there are 3574454 this is calculated by:
table = integerparttable(100);
>> sum(table(:,7))

This set would be given by:
parts = intpartgen(100,6);
(Which takes ~ 20 seconds to compute on my machine.)

If I later wanted to extend this set to all the partitions up to 110, I can pass this list back to the function so it doesn't have to recalculate them all

parts = intpartgen(110,6,parts);

Note that parts{k+1} is the partitions of k (since arrays start from 1 and the partition for 0 is included as part{1})

To calculate the number of ways to pay a sum of money at most 10 coins
>>> intlist = intpartgen2(value,10,[],[0,1,2,5,10,20,50,100]);
>>> ways_to_pay = intlist{value+1};
(for exactly 10 coins remove the value zero from allowed numbers)

Cite As

David Holdaway (2020). Integer partition generator (https://www.mathworks.com/matlabcentral/fileexchange/36437-integer-partition-generator), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (13)

Giorgia Calisti

David Holdaway

The "screen shot" is a set of Young diagrams which are a graphical representations of the sets the program calculates. The image is not generated by the program, it is a publicly available file on the Wikipedia commons, it's just a lot more interesting than pasting a screen shot of a table of numbers.

I will edit the file so the help is displayed as suggested, personally I never use help and just open any file and read the comments but if other people do it seems sensible to change that.

Ahsan Khan

I was wondering where did you acquire the screen shot? (of the tetris looking blocks)what is it displaying?

John D'Errico

There is still a problem with the help here. While there is a fair amount of help, what happens when you try to access it?

>> help intpartgen
lists all partitions of all integers up to N

>>

Yes, that is all you see. But if you edit the code, you find there is much more to be learned.

function intlist = intpartgen(N,maxnum,intlist)
%lists all partitions of all integers up to N

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% i.e. all the possible ways to express N as a sum of independent integers
% e.g. 3 = {3,2+1,1+1+1}, 4={4,3+1,2+1+1,2+2,1+1+1+1}...
%stored as 1d cell array with each cell containing

... yada, yada, yada, ...

The problem is, David has left blank lines in the help block. MATLAB dumps out only the FIRST CONTIGUOUS block of comments in a file. When you leave a blank, empty line, with no % in the beginning, this is a signal to the help utility to end the help.

So the only way to learn how to use these tools is to edit the code, or type it to the command window. Enticing the user to edit your code is a bad idea, as what if they accidentally modify it?

The point is, make it easy for help to work. Instead of a blank line between paragraphs, put in a blank comment line instead. The effort you spent on writing the help is wasted otherwise, as only you know it is there.

Jan

Yes, David, that's what I wanted to read. Now a user can decide, if this program is useful to solve his problem. I suggest to add this to the description on this page.

David Holdaway

There seems to be a lot of other good code written by people to solve similar problems which it is quite helpful to collate on one page!

However it seems I should clarify what this code does and why I bothered to write it rather than use the current programs on the FEX.

The main reason for the program was to generate quantum numbers for 1D many body harmonic oscillator states (of maxnum particles) below a cut off energy (N).

Say I wanted to generate all the partitions of the numbers 0-100, using at most 6 numbers. Of which there are 3574454 {calculated by
table = integerparttable(100);
>> sum(table(:,7)) }
This set would be given by
parts = intpartgen(100,6);
Which takes ~ 20 seconds to compute.

http://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer recursively calls itself which really can slow things down or even crash if it does so too many times. http://www.mathworks.com/matlabcentral/fileexchange/33616-integer-partitions does not allow you to limit partition length which would again make the calculation impossible.

This program can be used to add on more partitions given a smaller set (by passing this set as a 3rd input), but does not call itself when running.

John D'Errico

There is yet another partitions generator on the FEX.

http://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer

Jan

Thanks, Bruno. I had no doubt that David used the right term for the problem solved by his program. The term 'partition' appears in other fields also, compare: http://en.wikipedia.org/wiki/Partition ).
For this reason, and because it is a good idea in general when a function is posted in the FEX, I wanted to encourage him to improve the help text. The updated screen shot and description text is more helpful. Thanks, David.
A related submission: http://www.mathworks.com/matlabcentral/fileexchange/24185-partitions

Bruno Luong

To Jan: "Partition problem" is a standard and right word for this problem in mathematics and computer science.

Jan

Thanks for the clarifications, David. A lot of people use the FEX to search for new ideas. They have a problem and don't even know how it is called and they profit from exact definitions. On the other hand one cannot be sure, if a specific term like "partitions" is not used with a different meaning in other fields of science.
While the speed of my suggested method to set a row to ones might be negligible, the simplification of the code is always a good idea: High quality programs written by professionals have an error rate of about 1 bug per 1000 lines. Unfortunately leaner code is no guarantee for less bugs. But fatter code will contain more bugs ;-)

David Holdaway

Ah I see you were referring to the table file, while you may be correct this is such a trivial amount of time anyway (it is only calculated once) there doesn't seem to be much point in changing it, I will bear it in mind though.

David Holdaway

I'll update the help then, it just seems odd to me anyone who didn't know what was meant by integer partitions would bother looking for a program to calculate them. They are the number of unique (order independent) ways to express an integer "N" as a sum of positive integers, e.g. 3=3,2+1,1+1+1.
As for the recommendation on setting a column to one it's not entirely clear to me where I explicitly do that, I set a block of a matrix to another block of a matrix with an extra column of ones*j but would your method be faster for this?

Jan

I neither understand the description nor the the screenshot. Even the help sections are not clear to me. Most of all I'd defined at first, what "partitions" are.
Setting a column to 1 by "table(1,:) = uint32(ones(1,1+n))" is less efficient than: "table(1, :) = 1;", or if you want explicit casting: "table(1,:) = uint32(1);".

Updates

1.11.0.0

previously uploaded the wrong file!

1.10.0.0

Corrected help comments

1.9.0.0

Edited comment blocks to be continuous and show up when command "help" is used

1.8.0.0

Edited comment list to be one continuous block and thus show up when "help" is used

1.4.0.0

Version two allows the extra option of using only a restricted range of integers for the partition as well as a restricted number.

1.2.0.0

Updated Description to give example usage

1.1.0.0

Updated help, added feature to allow a cut off in partition length.

MATLAB Release Compatibility
Created with R2012a
Compatible with any release
Platform Compatibility
Windows macOS Linux