Code covered by the BSD License  

Highlights from
Partitions of an integer

Partitions of an integer

by

 

19 Aug 2006 (Updated )

List all partitions of an integer

partitions_demo

Contents

Find all (7) partitions of the number 5

partitions(5)
ans =
     5     0     0     0     0
     3     1     0     0     0
     1     2     0     0     0
     2     0     1     0     0
     0     1     1     0     0
     1     0     0     1     0
     0     0     0     0     1

Find all ways to break a dollar into coins of denomination [1 5 10 25 50]

plist = partitions(100,[1 5 10 25 50]);
% There are 292 of them...
size(plist,1)

plist
ans =
   292
plist =
   100     0     0     0     0
    95     1     0     0     0
    90     2     0     0     0
    85     3     0     0     0
    80     4     0     0     0
    75     5     0     0     0
    70     6     0     0     0
    65     7     0     0     0
    60     8     0     0     0
    55     9     0     0     0
    50    10     0     0     0
    45    11     0     0     0
    40    12     0     0     0
    35    13     0     0     0
    30    14     0     0     0
    25    15     0     0     0
    20    16     0     0     0
    15    17     0     0     0
    10    18     0     0     0
     5    19     0     0     0
     0    20     0     0     0
    90     0     1     0     0
    85     1     1     0     0
    80     2     1     0     0
    75     3     1     0     0
    70     4     1     0     0
    65     5     1     0     0
    60     6     1     0     0
    55     7     1     0     0
    50     8     1     0     0
    45     9     1     0     0
    40    10     1     0     0
    35    11     1     0     0
    30    12     1     0     0
    25    13     1     0     0
    20    14     1     0     0
    15    15     1     0     0
    10    16     1     0     0
     5    17     1     0     0
     0    18     1     0     0
    80     0     2     0     0
    75     1     2     0     0
    70     2     2     0     0
    65     3     2     0     0
    60     4     2     0     0
    55     5     2     0     0
    50     6     2     0     0
    45     7     2     0     0
    40     8     2     0     0
    35     9     2     0     0
    30    10     2     0     0
    25    11     2     0     0
    20    12     2     0     0
    15    13     2     0     0
    10    14     2     0     0
     5    15     2     0     0
     0    16     2     0     0
    70     0     3     0     0
    65     1     3     0     0
    60     2     3     0     0
    55     3     3     0     0
    50     4     3     0     0
    45     5     3     0     0
    40     6     3     0     0
    35     7     3     0     0
    30     8     3     0     0
    25     9     3     0     0
    20    10     3     0     0
    15    11     3     0     0
    10    12     3     0     0
     5    13     3     0     0
     0    14     3     0     0
    60     0     4     0     0
    55     1     4     0     0
    50     2     4     0     0
    45     3     4     0     0
    40     4     4     0     0
    35     5     4     0     0
    30     6     4     0     0
    25     7     4     0     0
    20     8     4     0     0
    15     9     4     0     0
    10    10     4     0     0
     5    11     4     0     0
     0    12     4     0     0
    50     0     5     0     0
    45     1     5     0     0
    40     2     5     0     0
    35     3     5     0     0
    30     4     5     0     0
    25     5     5     0     0
    20     6     5     0     0
    15     7     5     0     0
    10     8     5     0     0
     5     9     5     0     0
     0    10     5     0     0
    40     0     6     0     0
    35     1     6     0     0
    30     2     6     0     0
    25     3     6     0     0
    20     4     6     0     0
    15     5     6     0     0
    10     6     6     0     0
     5     7     6     0     0
     0     8     6     0     0
    30     0     7     0     0
    25     1     7     0     0
    20     2     7     0     0
    15     3     7     0     0
    10     4     7     0     0
     5     5     7     0     0
     0     6     7     0     0
    20     0     8     0     0
    15     1     8     0     0
    10     2     8     0     0
     5     3     8     0     0
     0     4     8     0     0
    10     0     9     0     0
     5     1     9     0     0
     0     2     9     0     0
     0     0    10     0     0
    75     0     0     1     0
    70     1     0     1     0
    65     2     0     1     0
    60     3     0     1     0
    55     4     0     1     0
    50     5     0     1     0
    45     6     0     1     0
    40     7     0     1     0
    35     8     0     1     0
    30     9     0     1     0
    25    10     0     1     0
    20    11     0     1     0
    15    12     0     1     0
    10    13     0     1     0
     5    14     0     1     0
     0    15     0     1     0
    65     0     1     1     0
    60     1     1     1     0
    55     2     1     1     0
    50     3     1     1     0
    45     4     1     1     0
    40     5     1     1     0
    35     6     1     1     0
    30     7     1     1     0
    25     8     1     1     0
    20     9     1     1     0
    15    10     1     1     0
    10    11     1     1     0
     5    12     1     1     0
     0    13     1     1     0
    55     0     2     1     0
    50     1     2     1     0
    45     2     2     1     0
    40     3     2     1     0
    35     4     2     1     0
    30     5     2     1     0
    25     6     2     1     0
    20     7     2     1     0
    15     8     2     1     0
    10     9     2     1     0
     5    10     2     1     0
     0    11     2     1     0
    45     0     3     1     0
    40     1     3     1     0
    35     2     3     1     0
    30     3     3     1     0
    25     4     3     1     0
    20     5     3     1     0
    15     6     3     1     0
    10     7     3     1     0
     5     8     3     1     0
     0     9     3     1     0
    35     0     4     1     0
    30     1     4     1     0
    25     2     4     1     0
    20     3     4     1     0
    15     4     4     1     0
    10     5     4     1     0
     5     6     4     1     0
     0     7     4     1     0
    25     0     5     1     0
    20     1     5     1     0
    15     2     5     1     0
    10     3     5     1     0
     5     4     5     1     0
     0     5     5     1     0
    15     0     6     1     0
    10     1     6     1     0
     5     2     6     1     0
     0     3     6     1     0
     5     0     7     1     0
     0     1     7     1     0
    50     0     0     2     0
    45     1     0     2     0
    40     2     0     2     0
    35     3     0     2     0
    30     4     0     2     0
    25     5     0     2     0
    20     6     0     2     0
    15     7     0     2     0
    10     8     0     2     0
     5     9     0     2     0
     0    10     0     2     0
    40     0     1     2     0
    35     1     1     2     0
    30     2     1     2     0
    25     3     1     2     0
    20     4     1     2     0
    15     5     1     2     0
    10     6     1     2     0
     5     7     1     2     0
     0     8     1     2     0
    30     0     2     2     0
    25     1     2     2     0
    20     2     2     2     0
    15     3     2     2     0
    10     4     2     2     0
     5     5     2     2     0
     0     6     2     2     0
    20     0     3     2     0
    15     1     3     2     0
    10     2     3     2     0
     5     3     3     2     0
     0     4     3     2     0
    10     0     4     2     0
     5     1     4     2     0
     0     2     4     2     0
     0     0     5     2     0
    25     0     0     3     0
    20     1     0     3     0
    15     2     0     3     0
    10     3     0     3     0
     5     4     0     3     0
     0     5     0     3     0
    15     0     1     3     0
    10     1     1     3     0
     5     2     1     3     0
     0     3     1     3     0
     5     0     2     3     0
     0     1     2     3     0
     0     0     0     4     0
    50     0     0     0     1
    45     1     0     0     1
    40     2     0     0     1
    35     3     0     0     1
    30     4     0     0     1
    25     5     0     0     1
    20     6     0     0     1
    15     7     0     0     1
    10     8     0     0     1
     5     9     0     0     1
     0    10     0     0     1
    40     0     1     0     1
    35     1     1     0     1
    30     2     1     0     1
    25     3     1     0     1
    20     4     1     0     1
    15     5     1     0     1
    10     6     1     0     1
     5     7     1     0     1
     0     8     1     0     1
    30     0     2     0     1
    25     1     2     0     1
    20     2     2     0     1
    15     3     2     0     1
    10     4     2     0     1
     5     5     2     0     1
     0     6     2     0     1
    20     0     3     0     1
    15     1     3     0     1
    10     2     3     0     1
     5     3     3     0     1
     0     4     3     0     1
    10     0     4     0     1
     5     1     4     0     1
     0     2     4     0     1
     0     0     5     0     1
    25     0     0     1     1
    20     1     0     1     1
    15     2     0     1     1
    10     3     0     1     1
     5     4     0     1     1
     0     5     0     1     1
    15     0     1     1     1
    10     1     1     1     1
     5     2     1     1     1
     0     3     1     1     1
     5     0     2     1     1
     0     1     2     1     1
     0     0     0     2     1
     0     0     0     0     2

Break a dollar into coins of denomination [1 5 10 25 50], but use no more than 4 of any coin

This means no pennies. There are only 11 ways to do this.

plist = partitions(100,[1 5 10 25 50],4)
plist =
     0     4     3     2     0
     0     2     4     2     0
     0     3     1     3     0
     0     1     2     3     0
     0     0     0     4     0
     0     4     3     0     1
     0     2     4     0     1
     0     3     1     1     1
     0     1     2     1     1
     0     0     0     2     1
     0     0     0     0     2

Partitions of the number 13 into a sum of even integers

partitions(13,2:2:12)
% It can't be done, of course.
ans =
   Empty matrix: 0-by-6

Partitions of 29 into integers 1:29, but use no single element more than once

plist = partitions(25,1:29,1);
size(plist,1)
ans =
   142

Partitions of 100 into a sum of exactly 4 squares of the integers 1:9

partitions(100,(1:9).^2,[],4)
ans =
     0     0     0     0     4     0     0     0     0
     1     0     0     0     2     0     1     0     0
     2     0     0     0     0     0     2     0     0
     0     1     0     2     0     0     0     1     0
     1     0     2     0     0     0     0     0     1

Contact us