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!