Introduction

A uniform random integer partition of n means every partition of n has exactly the same probability. That requirement is stricter than it looks, because many intuitive generators are biased toward either many small parts or a few large parts.

Uniform Means Uniform Over Partitions, Not Over Choices

For n = 5, the partitions are:

• '5'
• '4 + 1'
• '3 + 2'
• '3 + 1 + 1'
• '2 + 2 + 1'
• '2 + 1 + 1 + 1'
• '1 + 1 + 1 + 1 + 1'

A correct sampler must produce each of those seven outcomes with probability 1/7.

That is why "pick random parts until the sum reaches n" does not work. The sequence of choices is not in one-to-one correspondence with partitions.

Count First, Then Sample

A standard exact approach is dynamic programming.

Define:

count(total, max_part) = number of partitions of total using parts of size at most max_part.

The recurrence is:

• use at least one max_part
• or skip max_part entirely

That becomes:

1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def count(total: int, max_part: int) -> int:
5    if total == 0:
6        return 1
7    if total < 0 or max_part == 0:
8        return 0
9    return count(total - max_part, max_part) + count(total, max_part - 1)

Now you can sample by walking this recursion tree and choosing branches proportionally to how many complete partitions lie below each branch.

A Runnable Uniform Sampler

1import random
2from functools import lru_cache
3
4@lru_cache(maxsize=None)
5def count(total: int, max_part: int) -> int:
6    if total == 0:
7        return 1
8    if total < 0 or max_part == 0:
9        return 0
10    return count(total - max_part, max_part) + count(total, max_part - 1)
11
12def sample_partition(n: int) -> list[int]:
13    total = n
14    max_part = n
15    result = []
16
17    while total > 0 and max_part > 0:
18        use_count = count(total - max_part, max_part) if total >= max_part else 0
19        skip_count = count(total, max_part - 1)
20        total_count = use_count + skip_count
21
22        pick = random.randrange(total_count)
23        if pick < use_count:
24            result.append(max_part)
25            total -= max_part
26        else:
27            max_part -= 1
28
29    return result
30
31for _ in range(5):
32    print(sample_partition(8))

This returns partitions in non-increasing order, which is the standard representation.

Why the Method Is Uniform

At each branching point, you choose between two sets of completions:

• partitions that include the current largest part
• partitions that do not include it

If you choose each branch in proportion to the number of complete partitions underneath it, then every final leaf in the decision tree receives the same total probability.

That is the key idea. You do not choose parts uniformly. You choose branches by partition counts.

A Small Verification Check

For small n, you can verify the sampler experimentally.

1from collections import Counter
2
3trials = 20000
4seen = Counter(tuple(sample_partition(5)) for _ in range(trials))
5
6for partition, freq in sorted(seen.items()):
7    print(partition, round(freq / trials, 3))

The frequencies should all be close to 1/7 for n = 5, allowing for ordinary sampling variation.

Performance Notes

Memoization makes the exact algorithm practical for small and medium values of n, but partition counts grow quickly.

That means large n brings two issues:

• the dynamic programming table gets bigger
• the integer counts themselves become very large

For many programming tasks, memoized recursion or a bottom-up table is enough. For much larger combinatorial work, specialized algorithms from the random-partition literature may be more appropriate.

Common Pitfalls

The biggest mistake is sampling construction steps uniformly and assuming the final partitions are uniform. They are not.

Another mistake is forgetting that order does not matter in partitions. If order matters, you are sampling compositions, which is a different problem entirely.

A third issue is computing partition counts correctly but then choosing the two recursion branches with equal probability instead of count-weighted probability.

Finally, omitting memoization makes the exact method much slower than it needs to be.

Summary

• Uniform random partition sampling means every partition of n is equally likely.
• The reliable exact method is dynamic programming plus count-weighted sampling.
• Branches must be selected in proportion to how many full partitions lie underneath them.
• Partitions are unordered; do not confuse them with compositions.
• Memoization makes the exact sampler practical for many values of n.
• The key idea is count first, sample second.