Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Generate uniform random partitions of a number

by ambrus (Abbot)
on Sep 25, 2008 at 16:00 UTC ( [id://713669]=CUFP: print w/replies, xml ) Need Help??

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); }

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

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.

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

      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: CUFP [id://713669]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2024-03-29 15:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found