Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Re^4: Generator of integer partitionts of n

by hv (Parson)
on Aug 31, 2004 at 13:36 UTC ( #387182=note: print w/replies, xml ) Need Help??

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

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.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://387182]
and snow settles gently...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2018-06-24 00:34 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (126 votes). Check out past polls.