Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
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 rifling through the Monastery: (5)
As of 2015-07-30 04:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls