Re: Decomposing sum to unique sets of summands

[blokhead]

Here is a slightly simpler iterator than jethro's, but surely it's doing the same thing. It avoids the recursion blowup of JavaFan.

sub iterator {
  return unless @_;

  my @p = ($_[0]);
  return sub {

    ## collect all the trailing 2s, and last trailing 3 if present
    my $temp = 0;
    $temp += pop @p while @p and $p[-1] == 2;
    $temp += pop @p if    @p and $p[-1] == 3;    ## updated
    return if ! @p;

    ## reduce the last guy by 1, avoid total of 1 leftover
    $p[-1]--, $temp++;
    $p[-1]--, $temp++  if $temp == 1;

    ## redistribute collected amount, as large as possible
    ## (largest increments can be $p[-1])
    if ($temp % $p[-1] == 0) {
        push @p, ($p[-1]) x ($temp/$p[-1]);

    ## special case to avoid 1 leftover
    } elsif ( $temp % $p[-1] == 1 ) {
        my $m = int ($temp/$p[-1]) -1;
        push @p, ($p[-1]) x $m, $p[-1]-1, 2;

    } else {
        my $m = int ($temp/$p[-1]) ;
        push @p, ($p[-1]) x $m, ($temp - $p[-1]*$m);
    }

    @p;
  }
}

my $iter = iterator(shift || 50);

while (my @part = $iter->()) {
    print "@part\n";
}

Like jethro's, there could be some efficiencies gained by keeping track of some pointers, but the main problem is that there are just so many partitions. So I think the problem statement should be clarified, especially if 10^6 is involved.

Update: updated the marked line according to BrowserUk's suggestion. (added "@p and").

[BrowserUk]

Line 13 should be $temp += pop @p if @p and $p[-1] == 3; otherwise you get a warning for inputs divisible by 2;