Welcome to the Monastery 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?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (9)
As of 2018-03-20 10:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (250 votes). Check out past polls.

Notices?