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

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.

Hugo


Comment on Re^4: Generator of integer partitionts of n
Select or Download Code

Log In?
Username:
Password:

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

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

    April first is:







    Results (554 votes), past polls