A physical algorithm that finds all integer partitions of a number

Question

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!

Answer 1

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.

Answer 2

I've implemented a short C program for you

#include <stdio.h>

int CountIntDecompositions(int n, int lower_bound, int coins[], int coinIndex)
{
    if (n < 0)
        return -1;

    if (n == 0)
    {
        printf("(%d%", coins[0]);
        for (int i = 1; i < coinIndex; ++i)
            printf(", %d", coins[i]);
        printf(")\n");
        return 1;
    }

    int numWays = 0;
    for (int coin = lower_bound; coin <= n; ++coin)
    {
        coins[coinIndex] = coin;
        int ways = CountIntDecompositions(n - coin, coin, coins, coinIndex + 1);
        if (ways != -1)
            numWays += ways;
    }

    return numWays;
}

int main()
{
    int coins[11] = { 0 };
    int numWays = CountIntDecompositions(11, 1, coins, 0);
    printf("Total num of ways %d\n", numWays);
    return 0;
}

You can call it a physical algorithm, it prints out every possible way of integer decomposition - once.

The algorithm gradually increases the next lowest int value to pick. I've used "coins" as i think initially i was used to change. You can generalize to only available integer values (instead of increasing coin value by 1, you proceed to next available value)