Tag Archives: Partitions

Integer partitions in Python

These functions produce integer partitions in reverse lexicographic and lexicographic order respectively.

def revlex_partitions(n):
    """
    Generate all integer partitions of n
    in reverse lexicographic order
    """
    if n == 0:
        yield []
        return
    for p in revlex_partitions(n - 1):
        if len(p) == 1 or (len(p) > 1 and p[-1] < p[-2]):
            p[-1] += 1
            yield p
            p[-1] -= 1
        p.append(1)
        yield p
        p.pop()

def lex_partitions(n):
    """
    Generate all integer partitions of n
    in lexicographic order
    """
    if n == 0:
        yield []
        return
    for p in lex_partitions(n - 1):
        p.append(1)
        yield p
        p.pop()
        if len(p) == 1 or (len(p) > 1 and p[-1] < p[-2]):
            p[-1] += 1
            yield p
            p[-1] -= 1

Example program:

def main():
    for p in revlex_partitions(5):
        print(p)
    print()
    for p in lex_partitions(5):
        print(p)

if __name__ == '__main__':
    main()

Output:

[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]

[1, 1, 1, 1, 1]
[2, 1, 1, 1]
[2, 2, 1]
[3, 1, 1]
[3, 2]
[4, 1]
[5]

Reference: David Eppstein, IntegerPartitions.py

Partition function using dynamic programming in C

A partition of an integer is a way of writing it as a sum of positive integers. For example, partitions of 5 are:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

The order of numbers in a partition doesn’t matter. The number of partitions of a number \(n\) is given by the partition function \(p(n)\).

The first few values of \(p(n)\) are 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, … (A000041).

The partition function can be computed using a dynamic programming table-filling algorithm. Here it is in C:

#include <stdlib.h>

unsigned int partition(unsigned int n)
{
    unsigned int i, j;
    unsigned int result;
    unsigned int **table;

    if (n == 0) {
        return 1;
    }
   
    table = malloc((n + 1) * sizeof(unsigned int *));
    for (i = 0; i <= n; i++) {
        table[i] = malloc((n + 1) * sizeof(unsigned int));
    }

    for (i = 0;i <= n; i++) {
        table[i][0]=0;
    }
    for (i = 1; i <= n; i++) {
        table[0][i] = 1;
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (j > i) {
                table[i][j] = table[i][j - 1];
            }
            else {
                table[i][j] = table[i][j - 1] + table[i - j][j];
            }
        }
    }

    result = table[n][n];
    for (i = 0; i <= n; i++) {
        free(table[i]);
    }
    free(table);

    return result;
}

Example program:

#include <stdio.h>

int main(void) 
{
    unsigned int i;
    for (i = 0; i < 31; i++) {
        printf("%d\n",partition(i));
    }

    return 0;
}

Output:

1
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
231
297
385
490
627
792
1002
1255
1575
1958
2436
3010
3718
4565
5604

Partitions

A partition of a set is a division of it into disjoint subsets whose union is the set itself.

For example, the partitions of the set {a, b, c, d} are:

{{a, b, c, d}}
{{a, b, c}, {d}}
{{a, b, d}, {c}}
{{a, b}, {c, d}}
{{a, b}, {c}, {d}}
{{a, c, d}, {b}}
{{a, c}, {b, d}}
{{a, c}, {b}, {d}}
{{a, d}, {b, c}}
{{a}, {b, c, d}}
{{a}, {b, c}, {d}}
{{a, d}, {b}, {c}}
{{a}, {b, d}, {c}}
{{a}, {b}, {c, d}}
{{a}, {b}, {c}, {d}}

The scheme I am using is as follows: a partition is represented by an array of the same size as the set, and each element in the array is an integer specifying the subset in the partition in which the corresponding element occurs. For example, the array [0, 0, 0, 0] indicates that every element occurs in set 0, the first set, i.e., the partition {{a, b, c, d}}, while the array [0, 1, 2, 3] puts every element in its own set, i.e., the partition {{a}, {b}, {c}, {d}}.

The correspondences for the partitions of a 4-set are as follows:

[0, 0, 0, 0] = {{a, b, c, d}}
[0, 0, 0, 1] = {{a, b, c}, {d}}
[0, 0, 1, 0] = {{a, b, d}, {c}}
[0, 0, 1, 1] = {{a, b}, {c, d}}
[0, 0, 1, 2] = {{a, b}, {c}, {d}}
[0, 1, 0, 0] = {{a, c, d}, {b}}
[0, 1, 0, 1] = {{a, c}, {b, d}}
[0, 1, 0, 2] = {{a, c}, {b}, {d}}
[0, 1, 1, 0] = {{a, d}, {b, c}}
[0, 1, 1, 1] = {{a}, {b, c, d}}
[0, 1, 1, 2] = {{a}, {b, c}, {d}}
[0, 1, 2, 0] = {{a, d}, {b}, {c}}
[0, 1, 2, 1] = {{a}, {b, d}, {c}}
[0, 1, 2, 2] = {{a}, {b}, {c, d}}
[0, 1, 2, 3] = {{a}, {b}, {c}, {d}}

Having established how to represent partitions, the algorithm simply needs to produce the arrays shown above. At each step:

  1. Find the rightmost element that is no more than any element to its left
  2. Increment it
  3. Set all of the elements after it to 0
unsigned int next_partition(unsigned int *ar, size_t len)
{	
	unsigned int result = 0;
	if (ar[len - 1] < len - 1) {
		unsigned int i;
		unsigned int finished = 0;
		unsigned int changed = 0;
		/* Find the rightmost element no more than the other elements */
		for (i = len - 1; !finished && !changed; i--) {
			unsigned int j, max = 0;
			/* Find the highest element to the left of this one */
			for (j = 0; j < i; j++) {
				if (ar[j] > max) {
					max = ar[j];
				}
			}
			if (ar[i] <= max) {
				/* Increment */
				ar[i]++;
				changed = 1;
				/* Set the following elements to 0 */
				for (j = i + 1; j < len; j++) {
					ar[j] = 0;
				}
			}
			finished = i == 1;
		}
		result = 1;
	}

	return result;
}