Perl Monk, Perl Meditation 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);
}
}
[download]```
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
[download]```
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);
}
}
[download]```

-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
[download]```
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.

blokhead

Re^2: Generator of integer partitionts of n
by chiburashka on Aug 28, 2004 at 02:49 UTC
Thank you sooooooo much , that's Exactly what i was trying to do, but i need to get this output into an array somehow line by line, can you help just a little bit more please ?
```my @p;
sub part
{
my (\$a, \$k, \$n, \$t) = @_;
\$n = 2*\$k unless (defined(\$n));
\$t = 0    unless (defined(\$t));
\$p[\$t] = \$k;
push(@\$a, [ @p[1..\$#p] ]) if \$n == \$k;
for (my \$j = \$k<\$n-\$k ? \$k : \$n-\$k; \$j >= 1; \$j--) {
part(\$a, \$j, \$n-\$k, \$t+1);
}
}

my \$integer = ...;
my @a;
part(\@a, \$integer);
print(join(" ", @\$_), "\n") foreach (@a);
[download]```
Some random advice for you.

Depending on what you're doing, you should reconsider your desire to keep this data in an array. As n grows, the data requirements for that array grow rapidly. Once you use up available RAM (which happens sooner than you'd think), you're in trouble.

Changing your flow of control of your actual problem to avoid having to have it all in memory at once will let you calculate several more values of whatever you're trying to calculate.

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://386540]
help
Chatterbox?
 [1nickt]: chacham I have wanted to, and dones so, and so stated in a reply, and been roundly downvoted 2-1. (I assume for attempting to censor.) [1nickt]: pryrt yes, I see. There is no way to differentiate without forcing to a string and all sort of weird stuff. It is enough. User 42 can get creative if s/he wishes. [chacham]: i sent him a private message expressing my displeasure.

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (11)
As of 2017-05-24 20:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (186 votes). Check out past polls.