Pathologically Eclectic Rubbish Lister | |
PerlMonks |
Generate uniform random partitions of a numberby 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.
Then randpart($n) generates a random partition with uniform probablity among all partitions of the positive integer $n. As an example, run this.
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.
Back to
Cool Uses for Perl
|
|