# Generating Partitions

Python code for generating all integer partitions of a given integer $n > 0$
using different algorithms. Let's define some terminology.

**Integer partition:** An integer partition is a way to write a nonnegative integer $n$
as sum of positive integers (note that the order of the summand doesn't matter). Therefore,
3+2 and 2+3 are the same partitions of 5. The number of partition of $n$ is denoted by
$p(n)$. The function $p(\cdot)$ is called the _partition function_.

Example: There are 7 partitions of 5. Therefore, $p(5) = 7$.

\begin{align}
5 &= 1 + 1 + 1 + 1 + 1 \\
  &= 2 + 1 + 1 + 1 \\
  &= 2 + 2 + 1 \\
  &= 3 + 1 + 1 \\
  &= 3 + 2 \\
  &= 4 + 1 \\
  &= 5.
\end{align}

**Ascending/Descending composition:** Partitions are represented as an ordered list of
summands. Depending on whether they are ordered as weakly increasing or decreasing, it's
called either an _ascending_ or _descending composition_.

For example, `[2, 2, 1]` is a descending composition, whereas, `[1, 4]` is an ascending
composition.

**Ordering of the output:** An algorithm to generate all integer partitions may output the partition of the given input $n > 0$ in different order. Most commonly, they output the partitions as _lexicographically increasing_ or _decreasing_ order as list of summands.
This is independent of whether partitions are represented as ascending or descending
compositions.


```python
import partition
```


```python
dir(partition)
```




    ['__builtins__',
     '__doc__',
     '__file__',
     '__name__',
     '__package__',
     'accel_asc',
     'accel_desc',
     'merca1',
     'merca2',
     'merca3',
     'rule_asc',
     'rule_desc',
     'zs1',
     'zs2']



## ZS Algorithms (1998)

See [Zoghbi-Stojmenovic-1998] for reference. There are two algorithms, `zs1` and `zs2`.


```python
def print_partitions(algo_name, n):
    """Print all integer partions of n using the given algorithm.
    
    Inputs:
        n            A nonnegative integer
        algo_name    The algorithm name (a string)
    """
    method = getattr(partition, algo_name)
    for p in method(n):
        print p
        
def count_partitions(algo_name, n):
    """Count the number of all integer partitions of n using the given algorithm.

    Inputs:
        n            A nonnegative integer
        algo_name    The algorithm name (a string)
        
    Returns:
        The count, p(n) (integer or long).
    """
    method = getattr(partition, algo_name)
    count = 0
    for p in method(n):
        count += 1
    return count

# We will print partitions of a small number
n = 5
```


```python
print_partitions('zs1', n)
```

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


As we can see, `zs1` outputs partitions as descending compositions in lexicographically decreasing order.


```python
print_partitions('zs2', n)
```

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


`zs2` generates partitions as descending compositions, but in lexicographically increasing order.

Now let's compare the time to generate partiton of a large number (say N = 50). We won't print out the partitions, only count them.

Notice that the pure python implementation is much slower than the C implementation.

**TODO:** Later I will wrap the C program as a python module. Or, try other optimizations.


```python
# Define ans in the global scope:
ans = 0

# Moderately large number to test
N = 50

# It may take a long time
%timeit global ans; ans = count_partitions('zs1', N)
print ans
```

    10 loops, best of 3: 124 ms per loop
    204226



```python
%timeit global ans; ans = count_partitions('zs2', N)
print ans
```

    10 loops, best of 3: 161 ms per loop
    204226


## Kelleher's Algorithms (2006)

See [Kelleher-2006] for reference.  There are four algorithms: `rule_desc`, `rule_asc`, `accel_desc` and `accel_desc`.


```python
print_partitions('rule_desc', n)
```

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


The `rule_desc` algorithm generates partitions as descending compositions, in lexicographically decreasing order.


```python
print_partitions('rule_asc', n)
```

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


The `rule_asc` algorithm generates partitions as ascending compositions, in lexicographically increasing order.


```python
print_partitions('accel_desc', n)
```

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



```python
print_partitions('accel_asc', n)
```

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


The algorithms `accel_desc` and `accel_asc` are faster versions of `rule_desc` and `rule_asc` respectively.

Now, let's compare the speed.


```python
%timeit global ans; ans = count_partitions('rule_desc', N)
print ans
```

    1 loop, best of 3: 374 ms per loop
    204226



```python
%timeit global ans; ans = count_partitions('rule_asc', N)
print ans
```

    10 loops, best of 3: 159 ms per loop
    204226



```python
%timeit global ans; ans = count_partitions('accel_desc', N)
print ans
```

    10 loops, best of 3: 126 ms per loop
    204226



```python
%timeit global ans; ans = count_partitions('accel_asc', N)
print ans
```

    10 loops, best of 3: 124 ms per loop
    204226


## Merca's Algorithms

See [Merca-2012] for reference. There are three algorithms in this family: `merca1`, `merca2` and `merca3` -- all generates partitions as ascending compositions and in lexicographically increasing order.


```python
print_partitions('merca1', n)
```

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



```python
print_partitions('merca2', n)
```

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



```python
print_partitions('merca3', n)
```

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



```python
%timeit global ans; ans = count_partitions('merca1', N)
print ans
```

    1 loop, best of 3: 141 ms per loop
    204226



```python
%timeit global ans; ans = count_partitions('merca2', N)
print ans
```

    10 loops, best of 3: 122 ms per loop
    204226



```python
%timeit global ans; ans = count_partitions('merca3', N)
print ans
```

    10 loops, best of 3: 112 ms per loop
    204226



```python

```

8e3ea646045a6aca280c68caf92fd6587479eb24
ipynb
Jupyter Notebook
partition-examples.ipynb
deehzee/integer-partitions
7b2d1c6261d096fa59dd02d0acb42af8d71f9cd0
MIT
2017-01-03T20:51:55.000Z
2021-07-16T06:25:01.000Z
partition-examples.ipynb
deehzee/integer-partitions
7b2d1c6261d096fa59dd02d0acb42af8d71f9cd0
MIT
partition-examples.ipynb
deehzee/integer-partitions
7b2d1c6261d096fa59dd02d0acb42af8d71f9cd0
MIT
Qwen/Qwen-72B
1. YES
2. YES