Welcome to the Monastery PerlMonks

### Re^2: Generator of integer partitionts of n

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

in reply to Re: Generator of integer partitionts of n
in thread Generator of integer partitionts of n

if u don't mind, i want the fun, but i'm having this fun ,since yesterday(without sleep), i'm soo stuck here, please help me, SOS...
and also i've read too much quantum chemistry, so it's kind of hard to think about anything that loops for a little while.
• Comment on Re^2: Generator of integer partitionts of n

Replies are listed 'Best First'.
Re^3: Generator of integer partitionts of n
by hv (Parson) on Aug 28, 2004 at 11:49 UTC

I'd do it something like this:

```  use strict;

my \$n = shift @ARGV;
my \$try = [ \$n ];
while (\$try) {
print join(' ', @\$try), "\n";
\$try = next_partition(\$try);
}
exit 0; # all done

sub next_partition {
my \$current = shift;  # an arrayref of numbers in descending order

# find the last entry greater than one
my \$i;
for (\$i = 0; \$i < @\$current; ++\$i) {
last if \$current->[\$i] == 1;
}
--\$i;

# if all ones, there is no next partition
return undef if \$i < 0;

# we'll strip off all the ones, and one more
my \$count = @\$current - \$i;
# and must generate the first partition of that count
# subject to a top limit of what's to our left
my \$limit = --\$current->[\$i];

# replace the ones
splice @\$current, \$i + 1, \$count - 1,
# with the first paritition (limited) of the count
(\$limit) x int(\$count / \$limit), grep \$_, \$count % \$limit;
\$current;
}

Here's a variant of the same code that stores the current partition as a packed string of bytes instead of an arrayref of integers:

```  my \$n = shift @ARGV;
my \$try = chr(\$n);
while (defined \$try) {
print join(' ', map ord(\$_), split //, \$try), "\n";
\$try = next_partition(\$try);
}

sub next_partition {
my \$current = shift;  # a string of bytes in descending order

# find the last entry greater than one
\$current =~ s{ ([^\001]) (\001*) \z }{
my \$count = length(\$2) + 1;
my \$limit = ord(\$1) - 1;
my \$tail = \$count % \$limit;
(chr(\$limit) x int(1 + \$count / \$limit)) . (\$tail ? chr(\$tail) :
+ '')
}xe ? \$current : undef;
}

This should be rather more efficient than the arrayref variant, though obviously it can only find partitions for \$n < 256.

Update: silly me, in modern perls this will do the right thing even for much larger values of \$n.

Hugo

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (9)
As of 2018-06-17 22:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (107 votes). Check out past polls.

Notices?