Re^3: Generator of integer partitionts of n

[hv]

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;
  }

[hv]

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