Pathologically Eclectic Rubbish Lister PerlMonks

### Re: Generator of integer partitionts of n

by Limbic~Region (Chancellor)
 on Sep 25, 2004 at 14:40 UTC ( #393792=note: print w/replies, xml ) Need Help??

in reply to Generator of integer partitionts of n

chiburashka,
Here is an iterative solution that produces output in ascending order and is about twice as fast as blokhead's in my rudimentary benchmarks.
```#!/usr/bin/perl
use strict;
use warnings;

my \$numb = \$ARGV[ 0 ] || 10;
my \$iter = partition( \$numb );

while ( my @part = \$iter->() ) {
print "@part\n";
}

sub partition {
my \$target = shift;
return sub { () } if ! \$target || \$target =~ /\D/;

my @part = (0, (1) x (\$target - 1));
my \$done = undef;

return sub {
return () if \$done;

my \$min = \$part[ -2 ];
my \$total = \$part[ 0 ] ? 0 : 1;
my \$index = 0;

for ( 0 .. \$#part - 1) {
if ( \$part[ \$_ ] > \$min ) {
\$total += \$part[ \$_ ];
next;
}
\$index = \$_;
last;
}
\$part[ \$index ]++;

\$total += \$part[ \$index ];
if ( \$total > \$target || \$part[ \$index ] > \$part[ 0 ] ) {
@part = ( \$index ? ++\$part[ 0 ] : \$part[ 0 ], (1) x (\$targ
+et - \$part[ 0 ]) );
}
else {
@part = ( @part[ 0 .. \$index ], (1) x (\$target - \$total) )
+;
push @part , 1 if \$part[ 0 ] == 1;
}

\$done = 1 if \$part[ 0 ] == \$target;
return @part;
}
}
I am sure it could probably be improved a bit more but it is working and that's what's important.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://393792]
help
Chatterbox?
 [ambrus]: I'm currently in the process of rewriting my proof of concept programs. They sort of developped organically as I was experimenting, so now I've got an ugly mess of multiple programs and one-liners held together by nothing. I'll have to rewrite them to som [ambrus]: ething that's both cleanly organized and mostly automated. LanX in train, bad connection [Corion]: ambrus: Yeah - we're in that situation too, except that there is no time to do the reorganizing :-/ [LanX]: ... so my boss started a project with the newest sun servers and invited the traders to come on weekend to test it... and they were so pleased, that they forced him to keep it in production... [ambrus]: Corion: sure, this is the long-term plan. The short term is that I have to run this ungodly mess to get results from the new input data today. [Corion]: ambrus: Most of our "automation" is tied to process exit codes and a shell pipeline :-\ [LanX]: ... a week later they realized that one of the databases - which recorded how much the other banks due to this bank - was not correctly plugged

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (16)
As of 2017-03-29 11:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should Pluto Get Its Planethood Back?

Results (350 votes). Check out past polls.