Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^3: Generator of integer partitionts of n

by hv (Parson)
on Aug 28, 2004 at 11:49 UTC ( #386593=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Generator of integer partitionts of n
in thread Generator of integer partitionts of n

I'd do it something like this:

use strict; my $n = shift @ARGV; my $try = [ $n ]; while ($try) { print join(' ', @$try), "\n"; $try = next_partition($try); } exit 0; # all done sub next_partition { my $current = shift; # an arrayref of numbers in descending order # find the last entry greater than one my $i; for ($i = 0; $i < @$current; ++$i) { last if $current->[$i] == 1; } --$i; # if all ones, there is no next partition return undef if $i < 0; # we'll strip off all the ones, and one more my $count = @$current - $i; # and must generate the first partition of that count # subject to a top limit of what's to our left my $limit = --$current->[$i]; # replace the ones splice @$current, $i + 1, $count - 1, # with the first paritition (limited) of the count ($limit) x int($count / $limit), grep $_, $count % $limit; $current; }


Comment on Re^3: Generator of integer partitionts of n
Download Code
Re^4: Generator of integer partitionts of n
by hv (Parson) on Aug 31, 2004 at 13:36 UTC

    Here's a variant of the same code that stores the current partition as a packed string of bytes instead of an arrayref of integers:

    my $n = shift @ARGV; my $try = chr($n); while (defined $try) { print join(' ', map ord($_), split //, $try), "\n"; $try = next_partition($try); } sub next_partition { my $current = shift; # a string of bytes in descending order # find the last entry greater than one $current =~ s{ ([^\001]) (\001*) \z }{ my $count = length($2) + 1; my $limit = ord($1) - 1; my $tail = $count % $limit; (chr($limit) x int(1 + $count / $limit)) . ($tail ? chr($tail) : + '') }xe ? $current : undef; }

    This should be rather more efficient than the arrayref variant, though obviously it can only find partitions for $n < 256.

    Update: silly me, in modern perls this will do the right thing even for much larger values of $n.

    Hugo

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (9)
As of 2014-08-29 20:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (287 votes), past polls