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.
Here is an iterative solution that produces output in ascending order and is about twice as fast as blokhead's in my rudimentary benchmarks.
I am sure it could probably be improved a bit more but it is working and that's what's important.#!/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; } }
Cheers - L~R
|
---|
In Section
Seekers of Perl Wisdom