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).
partitions of size 2 we do following.
Take 11 coins of identical widths. Take a paper. Write
2 on it
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
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
1 2 3 9c 1c 1c
1 2 3 8c 2c 1c
1 2 3 7c 3c 1c
1 2 3 7c 2c 2c
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!