1
$\begingroup$

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!

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.