No such thing as a small change PerlMonks

### Re: Generator of integer partitionts of n

by kvale (Monsignor)
 on Aug 28, 2004 at 02:35 UTC ( #386540=note: print w/replies, xml ) Need Help??

in reply to Generator of integer partitionts of n

Here is a different algorithm that seems to be simpler:
```my \$integer = 5;
my @p;
part( 2*\$integer, \$integer, 0);

sub part
{
my (\$n, \$k, \$t) = @_;
\$p[\$t] = \$k;
print( join " ", @p[1..\$#p], "\n") if  \$n == \$k;
for (my \$j = \$k<\$n-\$k ? \$k : \$n-\$k; \$j >= 1; \$j--) {
part( \$n-\$k, \$j, \$t+1);
}
}
which results in
```1004% perl part.pl
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
Update: Thanks to blokhead for catching my error! I had the correct algorithm, but blew it on the print statement. The last valid element of @p is at index \$t. Here is the corrected code:
```my \$integer = 5;
my @p;
part( 2*\$integer, \$integer, 0);

sub part
{
my (\$n, \$k, \$t) = @_;
\$p[\$t] = \$k;
print( join " ", @p[1..\$t], "\n") if  \$n == \$k;
for (my \$j = \$k<\$n-\$k ? \$k : \$n-\$k; \$j >= 1; \$j--) {
part( \$n-\$k, \$j, \$t+1);
}
}

-Mark

Replies are listed 'Best First'.
Re^2: Generator of integer partitionts of n
by blokhead (Monsignor) on Aug 28, 2004 at 07:02 UTC
Changing \$integer to 6 for example gives:
```6
5 1
4 2
4 1 1
3 3 1   # oops
3 2 1
3 1 1 1
2 2 2 1 # oops
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
You can check how many partitions of N exist for the first many values of N at this site. For N=10, for instance, there should be 77 and your script returns less than 50 (many of them even adding up to more than 10). Update: Other than an extra 1 on a few partitions here and there, it seems to get all of them though.

A reply falls below the community's threshold of quality. You may see it by logging in.

Create A New User
Node Status?
node history
Node Type: note [id://386540]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (10)
As of 2021-01-22 14:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (239 votes). Check out past polls.

Notices?