File Exchange

image thumbnail

Partitions of an integer

version 1.21.0.0 (5.61 KB) by John D'Errico
List all partitions of an integer

31 Downloads

Updated 11 Mar 2018

View License

The money changing problem is a simple one to state. For example, how many different ways can one form change of a dollar (100 cents) by using only coins of denomination [1 5 10 25 50] ? (The answer is 292.)
Its an example of a general problem, i.e., in how many unique ways can an integer be partitioned as a sum of smaller positive integers?
http://en.wikipedia.org/wiki/Integer_partition
I wrote partitions to solve the fully general problem, but it can be used with restrictions too. You can constrain the set of elements in the sum, and the maximum number of times any one elements can appear, as well as fixing the total number of terms that will appear in the final sum.
See the demo for a few examples of use.

Cite As

John D'Errico (2020). Partitions of an integer (https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (21)

Song Bai

Useful when implementing Polynomial Chaos Expansion! Thanks a lot!

Stephen Cobeldick

Reliable, well documented, and very useful. Does exactly what it says on the tin.

madhan ravi

John D'Errico

It turns out that I had found that bug myself, and repaired it, but I do humbly apologize that I had forgotten to post the repaired version. It is posted now.

yayun Hu

Hi, John D'Errico. Your code in line 197 is wrong, and it should be changed into
if (fixed_count*candidate_set) == total_sum && (fixed_count<=max_count)

yayun Hu

Hi, just want to ask if there is a bug in this bug?
Here is what I do not understand.
When running:
plist = partitions(10,[1:5],[1],[4])
I get the out put:
plist =

1 1 1 1 0
2 0 1 0 1.
This is not right since plist = partitions(10,[1:5],[1],[4]) means to partition 10 into four numbers from the set [1:5] , with each number appearing only once. Thus, the second row of output [2 01 0 1] does not make sense for the double appearance of number 1.

By the way, I will keep looking at this code because I do need to use it.

Marat Kurbangaleev

Alexander Eick

Nolan Conaway

marco falke

Flexible script

Marcin

Omar

Thanks a lot, I was looking for this function.

Kammoun

good work

John D'Errico

Suppose I wish to list out the integer partitions of 10, using the numbers [1,2,3,4]? The solutions are easy to delineate. Look at the largest element of the candidate members of the partition, in this case, pivot around the number 4. How many times can 4 potentially appear in that sum? Clearly, we may be able to form the total of 10 by including the number 4 a total of 0, 1, or 2 times. If so, then we can reduce the problem.

If 4 appears twice, then we need to find the list of all partitions of 10 - 2*4 = 2, made from the set [1,2,3].

If 4 appears once, then we need to find the list of all partitions of 10 - 1*4 = 6, made from the set [1,2,3].

If 4 appears not at all, then we need to find the list of all partitions of 10 - 0*4 = 10, made from the set [1,2,3].

I can rigorously argue that this procedure must generate all solutions, and do so rather efficiently, to the extent that is possible.

Now, call partitions to solve the problem. See that the last two solutions in the set have 4 appearing twice. There are exactly 2 ways to solve that problem. Before that, we see there were 7 ways to solve the partitions of 6. And there were 14 ways to solve the problem with 4 never appearing at all.

>> partitions(10,1:4)
ans =
10 0 0 0
8 1 0 0
6 2 0 0
4 3 0 0
2 4 0 0
0 5 0 0
7 0 1 0
5 1 1 0
3 2 1 0
1 3 1 0
4 0 2 0
2 1 2 0
0 2 2 0
1 0 3 0
6 0 0 1
4 1 0 1
2 2 0 1
0 3 0 1
3 0 1 1
1 1 1 1
0 0 2 1
2 0 0 2
0 1 0 2

While partitions has other arguments that complicate the problem slightly by constraining the solution, the basic approach is exactly the same. Simply pivot around the largest member of the set of candidates to form that sum. Once you have determined the number of times 4 may appear in the sum, you can forget about it, and then worry about the rest.

Of course, had I tried to solve the problem partitions(500,1:500) by this approach, this would be a rather time (and memory) consuming task. My vpi toolbox has a tool to enumerate the number of integer solutions:

>> numberOfPartitions(500)
ans =
2300165032574323995027

Or, if you prefer...

>> vpi2english(numberOfPartitions(500))
ans =
two sextillion, three hundred quintillion, one hundred sixty five quadrillion, thirty two trillion, five hundred seventy four billion, three hundred twenty three million, nine hundred ninety five thousand, twenty seven

But then, nothing I could do would solve that problem efficiently.

Arindra Guha

What algorithm is used or what is the theory behind how the partitions are generated by the program.

Sergei Koulayev

Thank you John! Its not an easy problem to solve yourself.

Senol Korkmaz

Rakib Ahmed

Excellent codes with helpful documentation.

Alexander Statnikov

Very helpful!

xiaole bai

Very good code! Very helpful!
Excellent !!!!

urs (us) schwarz

a very useful snippet distinguished by excellent help (including sources of its algorithm), intuitive examples as well as a demo package, exhaustive error checking, good guidance for programmers, and a sleek computational engine.

Updates

1.21.0.0

Comment change

1.2.0.0

Fix the plist=partitions(10,[1:5],[1],[4]) bug.

1.0.0.0

Added a new option: a user defined number of terms in the sum.

Version 1.1: Allow the candidate set to be non-decreasing rather than strictly increasing

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

Inspired by: partitiontable.m

Inspired: nsumk

partitions/html/