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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.