How do I generate a uniform random integer partition?

Question

A Google search reveals plenty about generating all possible partitions of an integer n into m parts, but I haven't found anything about sampling a uniformly distributed random partition of n into m parts.

Answer 1

After some googling I found an algorithm for this in the "Handbook of Applied Algorithms," which Google Books has indexed. The algorithm is given in section 1.12.2, on page 31.

Answer 2

Here is some code that does it. This is O(n²) the first time you call it, but it builds a cache so that subsequent calls are O(n).

import random

cache = {}

def count_partitions(n, limit):
    if n == 0:
        return 1
    if (n, limit) in cache:
        return cache[n, limit]
    x = cache[n, limit] = sum(count_partitions(n-k, k) for k in range(1, min(limit, n) + 1))
    return x

def random_partition(n):
    a = []
    limit = n
    total = count_partitions(n, limit)
    which = random.randrange(total)
    while n:
        for k in range(1, min(limit, n) + 1):
            count = count_partitions(n-k, k)
            if which < count:
                break
            which -= count
        a.append(k)
        limit = k
        n -= k
    return a

How this works: We can calculate how many partitions of an integer n there are in O(n²) time. As a side effect, this produces a table of size O(n²) which we can then use to generate the kth partition of n, for any integer k, in O(n) time.

So let total = the number of partitions. Pick a random number k from 0 to total - 1. Generate the kth partition.

Answer 3

Just one more version in c#.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication6
{
    class Program
    {
        static Random random = new Random();

        static void Main(string[] args)
        {
            PrintPartition(GetUniformPartition(24, 5));
            PrintPartition(GetUniformPartition(24, 5));
            PrintPartition(GetUniformPartition(24, 5));
            PrintPartition(GetUniformPartition(24, 5));
            PrintPartition(GetUniformPartition(24, 5));
            Console.ReadKey();
        }

        static int[] GetUniformPartition(int input, int parts)
        {
            if(input<= 0 || parts <= 0)
                throw new ArgumentException("invalid input or parts");
            if (input < MinUniformPartition(parts))
                throw new ArgumentException("input is to small");

            int[] partition = new int[parts];
            int sum = 0;
            for (int i = 0; i < parts-1; i++)
            {
                int max = input - MinUniformPartition(parts - i - 1) - sum;
                partition[i] = random.Next(parts - i, max);
                sum += partition[i];
            }
            partition[parts - 1] = input - sum; // last 
            return partition;
        }

        // sum of 1,2,3,4,..,n
        static int MinUniformPartition(int n)
        {
            return n * n - 1;
        }

        static void PrintPartition(int[] p)
        {
            for (int i = 0; i < p.Length; i++)
            {
                Console.Write("{0},", p[i]);
            }
            Console.WriteLine();
        }
    }
}

This code will produce next output:

5,8,7,2,2,
6,6,7,2,3,
5,7,6,2,4,
6,4,3,2,9,
7,8,4,4,1,