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 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9200542,"math_prob":0.98489195,"size":1993,"snap":"2022-05-2022-21","text_gpt3_token_len":536,"char_repetition_ratio":0.1417798,"word_repetition_ratio":0.041450776,"special_character_ratio":0.26141495,"punctuation_ratio":0.080684595,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95350116,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-19T00:42:29Z\",\"WARC-Record-ID\":\"<urn:uuid:2f2a99a9-0e17-4cfa-9d71-ae298bf65d77>\",\"Content-Length\":\"148976\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:1cb9534d-bfb8-437d-a088-cb7045283ffd>\",\"WARC-Concurrent-To\":\"<urn:uuid:7d4ab9b6-682a-46f5-ac28-e9d68ecf08d6>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/90911/a-physical-algorithm-that-finds-all-integer-partitions-of-a-number/90915#90915\",\"WARC-Payload-Digest\":\"sha1:EF3N3JWJUNFMOTDIPO75QI2VJHKJZBDC\",\"WARC-Block-Digest\":\"sha1:EOFBQMKQVA4OKW2MJ44BDLWJG7XDIRG3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320301217.83_warc_CC-MAIN-20220119003144-20220119033144-00523.warc.gz\"}"}