Perl Monk, Perl Meditation PerlMonks

Re: Generator of integer partitionts of n

by hv (Parson)
 on Aug 28, 2004 at 02:20 UTC ( #386537=note: print w/replies, xml ) Need Help??

in reply to Generator of integer partitionts of n

I think there are a variety of improvements that could be made to the style of the code.

Firstly, initialising @a and @b can be done rather more simply:

```  @aa = @bb = (1) x \$nn;
.. which removes the need for the variable \$n

Secondly, the @ready array is being built up an element at a time, starting from element zero. So it would be simpler to remove the index calculations, and just use push:

```  push @ready, "@aa\n";
...
...

\$kk is used to count down from the start value to 0, and I'd find it clearer to express that directly at the head of the loop:

```  for (my \$kk = \$nn; \$kk > 0; --\$kk) {
...
}

It also seems odd that you declare @ready with my(), but none of the other variables. While writing everything with use strict is a good habit to get into, since there are no function calls in this code nor variables declared inside blocks there isn't much to be gained here. However consistency is always good, and you should either declare all your variables that way or none of them.

I don't understand the algorithm you are using at all: when I run the code for small values of \$nn I get many warnings, and the results include many duplications, odd spacing, and some zeros. Also, this algorithm always produces exactly 3n results, which is too many for small values of n and too few for larger values. (The first example I noticed of a missing partition was for n = 6 = 2 + 2 + 2.)

If I were attempting to produce an algorithm for this, I'd be inclined to start off with the assumption that I'd want an iterator, so I'd consider first how to define a canonical ordering for a partition (eg with the numbers sorted in descending order), and then consider how given one partition I could generate the next one.

This is fairly easy to do if you define the iterator function to take an additional parameter, but I don't want to give too much away here in case you still want the fun of working it out for yourself.

Hugo

Replies are listed 'Best First'.
Re^2: Generator of integer partitionts of n
by chiburashka on Aug 28, 2004 at 02:28 UTC
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.

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://386537]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (7)
As of 2018-05-22 14:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (163 votes). Check out past polls.

Notices?