Generate uniform random partitions of a number

The following snippet shows how to generate uniform random partitions of a number fast.

Take the following definitions.

use strict; 
my %npart; sub cntpart1 { my($n, $m) = @_; $n = 0+$n; $m = 0+$m; my $c
+ = \$npart{$n." ".$m}; defined($$c) and return $$c; $n <= 0 and retur
+n $$c = 1; my $s = 0; for my $k (1 .. ($m < $n ? $m : $n)) { $s += cn
+tpart1($n - $k, $k); } $$c = $s; } 
sub randpart1 { my($n, $m) = @_; $n <= 0 and return; my($s, $k) = 0; f
+or my $j (1 .. ($m < $n ? $m : $n)) { my $p = cntpart1($n - $j, $j); 
+rand($s += $p) < $p and $k = $j; } $k, randpart1($n - $k, $k); } 
sub randpart { my($n) = @_; randpart1($n, $n); }
[download]

Then randpart($n) generates a random partition with uniform probablity among all partitions of the positive integer $n.

As an example, run this.

perl -we 'use strict; my %npart; sub cntpart1 { my($n, $m) = @_; $n = 
+0+$n; $m = 0+$m; my $c = \$npart{$n." ".$m}; defined($$c) and return 
+$$c; $n <= 0 and return $$c = 1; my $s = 0; for my $k (1 .. ($m < $n 
+? $m : $n)) { $s += cntpart1($n - $k, $k); } $$c = $s; } sub randpart
+1 { my($n, $m) = @_; $n <= 0 and return; my($s, $k) = 0; for my $j (1
+ .. ($m < $n ? $m : $n)) { my $p = cntpart1($n - $j, $j); rand($s += 
+$p) < $p and $k = $j; } $k, randpart1($n - $k, $k); } sub randpart { 
+my($n) = @_; randpart1($n, $n); } for (1 .. 10000) { print join(" ", 
+randpart($ARGV[0])), "\n"; }' 6 | sort | uniq -c
[download]

This quickly generates ten thousand random partitions of 6, and then sort | uniq builds a frequency table so you can see each of the eleven possible partitions are generated approximately the same number of times.

The function is fast even for larger $n values too. Internally it works by cntpart1($n, $m) calculating the number of partitions of $n with no partition greater than $m, and this count is memoized.

Update: You may want to add a no warnings "recursion";

Update 2008 sep 28: Limbic~Region referred me to his code RFC: Integer::Partition::Unrestricted which computes the number of partitions of any integer really fast. I'll have to read its implementation on whether it can help here.

Comment on Generate uniform random partitions of a number Select or Download Code

Replies are listed 'Best First'.
Re: Generate uniform random partitions of a number by blokhead (Monsignor) on Sep 25, 2008 at 20:45 UTC
Nice. I wonder if there is a more direct way to sample the distribution, instead of computing the number of partitions for each of the possible first choices (this appears to be what you do, although the code is too golfed for me to really parse). For this application, you don't need the actual number of such partitions, just their ratios. BTW, did you have in mind a cool application of uniformly sampling partitions, or was this just "because it's there"? ;) blokhead	[reply]
Re^2: Generate uniform random partitions of a number by ambrus (Abbot) on Sep 25, 2008 at 22:08 UTC
I'm holding a programming course and one of the homeworks I'm setting requries a partition of an integer as input. It's not really important that it's uniformly random, but I wanted to generate some sample inputs (and corresponding outputs) so the students can test their solutions on, and then I thought of this. It's a bit of an overkill because it needs like an hour to generate a partition of 5000, and the homework problem would work just as well if I just generated random partitions of any other distribution as test input, but the task carried me over. I posted it in case me or someone else really needs a uniformly random partition at one point. I'd have written it by hand for the challenge even if I knew of a pre-written function that can generate a random partition. If you know of such a function in any library (not necessarily perl), please tell, because it seems so obvious it must exist, yet I can't find any right now. Even mathematica doesn't seem to have a function that gives you the kth partitioning of the integer n or anything similar.	[reply]