Perl-Sensitive Sunglasses PerlMonks

### Re: Generator of integer partitionts of n

 on Aug 28, 2004 at 06:59 UTC ( #386571=note: print w/replies, xml ) Need Help??

in reply to Generator of integer partitionts of n

Sloane's Integer Sequences gives the number for partitions of N for many values of N. The first solution given in this thread (and the one in its reply) doesn't work. For instance, with N=10, it only gives 42 when it should give 77 (among other obviously invalid partitions it lists).

Here's one using an iterator. Since the number of partitions of N grows exponentially with N, it might be best to not have the entire set of partitions in memory. This is based off the algorithm outlined here.

```my \$n    = shift || 10;
my \$iter = int_partitions(\$n);
my \$total;

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

print "There are \$total partitions of \$n\n";

sub int_partitions {
my \$n = shift;
my @tally;

return sub {
if (!@tally) {
@tally = ( (0) x \$n, 1 );
return (\$n);
}

## last partition is \$n 1's
return if \$tally[1] == \$n;

## take one away from smallest >1 part
my (\$least) = grep { \$tally[\$_] } 2 .. \$n;

\$tally[\$least]--;
\$tally[\$least-1]++;
\$tally[1]++;

## collect multiple 1's into groups smaller than \$least
while ( \$least > 2 and \$tally[1] > 1 ) {
my \$move = ( sort { \$a <=> \$b } \$least-1, \$tally[1] )[0];
\$tally[1] -= \$move;
\$tally[\$move]++;
}

return map { (\$_) x \$tally[\$_] } reverse 1 .. \$n;
};
}
This returns partitions in decreasing lexicographic order. Cheers!

Update: Just for fun, here's code for iterating over all partitions of a set (also inspired from the article linked above):

```my @set  = @ARGV ? @ARGV : 1 .. 4;
my \$iter = set_partitions(@set);
my \$total;

while ( my @part = \$iter->() ) {
\$total++;
print join(" ", map { "[@\$_]" } @part), \$/;
}

print "There are \$total partitions of @set\n";

sub set_partitions {
my @universe = @_;
my @growth;

return sub {
if (!@growth) {
@growth = (0) x @universe;
return [ @universe ];
}

return if \$growth[-1] == \$#growth;

my \$i = \$#growth;
\$growth[\$i--] = 0 while \$growth[\$i-1] == \$growth[\$i] - 1;

\$growth[\$i]++;

my @return;
push @{ \$return[\$growth[\$_]] }, \$universe[\$_] for 0 .. \$#growt
+h;

return @return;
};
}
The internal order of parts is not significant. The parts are returned in ascending order of their smallest element. If the input set has duplicates, so will the output. I'd have to think about how to do this for multisets... Hey, this is fun! ;)

Create A New User
Node Status?
node history
Node Type: note [id://386571]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2017-06-27 20:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (613 votes). Check out past polls.