# A physical algorithm that finds all integer partitions of a number

If this is not the right forum for this question let me know.

I am looking for a physical algorithm that can be easily followed by anyone not knowing much mathematics to get integer partitions of a number.

I have come up with the following way - but there is an issue (described later).

Suppose I want to divide number 11 into all its integer partitions (order is not important).

For finding partitions of size 2 we do following.

Take 11 coins of identical widths. Take a paper. Write 1 and 2 on it

1    2


Below the first number, keep all 11 coins one upon another to make a tower of height 11. This is represented as -

1      2

11c   0c


Now, shift 1 coin from first column to second column.

1      2

10c   1c


Here, height of tower 1 = 10, height of tower2 = 1

Keep on doing this, only if Height of tower 1 >= Height of tower2

On each step of the algorithm, we get new integer partition.

• This "physical algorithm" is easy to understand by anyone knowing basic mathematics.
• Preferrably, each step in the physical algorithm must show a new partitioning way.
• There should be an end condition to the algorithm.
• When the algorithm reaches end condition, all possible partitioning ways must have been shown.

If we now want to find all partitions of size 3, the problem gets a bit tricky.

We have 3 towers, with following restrictions Height of tower 1 >= Height of tower2 >= Height of tower3

But thing is, there are certain positions, from which we cannot go to next stage without destroying earlier stage - what do I mean by this? See below

Step1

1      2     3

9c    1c     1c


Step2

1      2     3

8c    2c     1c


Step3

1      2     3

7c    3c     1c


Alternative Step3

1      2     3

7c    2c     2c


At step 3 the algorithm creates two branches - people could either put new coin in tower2 or tower1. How should the algorithm statements be written so that by the time the algorithm is finished, all partitions of size 3 are known?

If you could come up with a new algorithm, that's welcome too!

• either put new coin in tower2 or tower1 from 1 to either 2 or 3 – greybeard Apr 20 '18 at 4:08

Let us aim at generating the partitions in the following order (below, for $n=6$):

\begin{align*} & 6 \\ & 5 \, 1 \\ & 4 \, 2 \\ & 4 \, 1 \, 1 \\ & 3 \, 3 \\ & 3 \, 2 \, 1 \\ & 3 \, 1 \, 1 \, 1 \\ & 2 \, 2 \, 2 \\ & 2 \, 2 \, 1 \, 1 \\ & 2 \, 1 \, 1 \, 1 \, 1 \\ & 1 \, 1 \, 1 \, 1 \, 1 \, 1 \end{align*} We start with the partition $n$.

To generate a new partition, identify the last non-1 entry in the preceding partition (if there is no such, we’re done); reduce it by 1, and delete all following entries; complete it to a partition by repeatedly adding the maximum possible number, under the constraint that the partition is non-increasing.

You can check that this indeed generates all partitions.

I have come up with following algorithm for finding partitions of size 3. It may be generalized to size N, but I'm not 100% sure.

Initial Setup

A paper with 3 numbers, 1,2 and 3 written on it.

11 coins.

1 coin in tower1, 1 coin in tower2, 9 coins in tower3.

This is represented as

[step1] 1 1 9


Algorithm This algorithm is a series of steps. Some of the steps are termed "starting positions". Once a starting position is reached, an operation O1 must be performed to reach next step - while satisfying a certain condition C0. Then we repeat that operation multiple times. If that partular condition C0 cannot be satisfied, we go to the next starting position via operaiton O2.

Condition C0 = Height of tower1 <= Height of tower2 <= Height of tower3

Operation O1 = Shift one coin from last tower to second-last tower while condition C0 is satisfied. If C0 cannot be satisfied do operation O2

Operation O2 = Shift one coin from last tower to first tower. Then shift coins from second-last tower to last-tower until Height of tower1 = Height of tower2

Termination condition = If after performing operation O2, condition C0 cannot be satisfied, algorithm is terminated and that coin distribution is discarded.

Algorithm demonstration

Initial Starting position

[step1] 1 1 9


Condition C0 Height of tower1 <= Height of tower2 <= Height of tower3

Operation O1 -> Shift one coin from last tower to second-last tower while condition C0 is satisfied.

[step2] 1 2 8
[step3] 1 3 7
[step4] 1 4 6
[step5] 1 5 5


Now, we can no longer perform operation O1 without disobeying condition C0. So we shift to next starting position via operation O2 which modifies coin distribution according to some conditions.

Operation O2 - Shift one coin from last tower to first tower Shift coins from second-last tower to last-tower until Height of tower1 = Height of tower2

If condition C0 cannot be satisfied at this stage - algorithm is terminated. Otherwise we go forward as below

After performing operation O2 we reach next starting position as below

[step6] 2 2 7


Now, a series of O1 operations takes us through -

[step7] 2 3 6
[step8] 2 4 5


Now C0 cannot be obeyed after performing operation O1, so we apply operation O2

[step9] 3 3 5


Then another O1

[step10] 3 4 4


Now C0 cannot be obeyed after performing O1, so we apply O2

4 4 3


C0 cannot be obeyed by above distribution, so algorithm has terminated and last coin position 4 4 3 is discarded.

Thus we get all 10 ways to partition 11 into 3 summands.