TL;DR

Turning the recursive implementation in All positive integer sums to an iterator-based one.

For the purposes laid out in All positive integer sums to figure out all partitions of a set, it can be handy to have an iterator-based implementation, i.e. one where we don’t get all possible arrangements at once, but one next arrangement only when we ask for it.

This allows us to chain operations that take a specific input and expand it to zero, one, or multiple outputs, again with an iterator-based approach. At the end of the whole process, this will allow us to do something like this:

my $it = gimme_iterator(@args);
while (my $arrangement = $it->()) {
    printout($arrangement);
}

You get the idea.

The easiest way to turn the implementation we have into an iterator-based one is probably the following:

sub int_sums_recursive ($N, $max = undef) {
   return ([]) unless $N;
   $max = $N if ! defined($max) || $max > $N;
   my @retval;
   for my $first (reverse 1 .. $max) {
      push @retval, [$first, $_->@*]
         for int_sums_recursive($N - $first, $first);
   }
   return @retval;
}

sub int_sums_iterator ($N) {
   my @arrangements = int_sums_recursive($N);
   return sub { return shift @arrangements };
}

Although it might not seem too clever, this still has its merits because it allows us to start adhering to the iterator interface immediately. We might decide to start working on the other half of the problem immediately, or to concentrate on the iterator optimization immediately. Which, contrarily to any common sense, we will do immediately 😅

The implementation is not too different:

sub int_sums_iterator ($N, $max = undef) {
   if ($N < 1) {
      my @retvals = ([]);
      return sub { shift @retvals };
   }
   $max //= $N;
   my $first = $N < $max ? $N : $max;
   my $rit   = undef;
   return sub {
      my @retval;
      while ($first > 0) {
         $rit //= int_sums_iterator($N - $first, $first);
         if (my $rest = $rit->()) {
            return [$first, $rest->@*];
         }
         ($first, $rit) = ($first - 1, undef);
      }
      return;
   }
}

One important thing that has to be settle down early on is what return value we want to give. An iterator should have a non-ambiguous way of saying that the sequence is exhausted, which in our case might be to return undef/empty list with a simple lone return.

This leaves us with dealing with the basic case where $N is less than $1$, i.e. we have to generate a decomposition of $0$ with only positive integer values - that is, an empty list.

For this reason, we will return the lists (even an empty one) within an array reference, so that even an empty list will be a defined scalar. This accounts for the base case at the beginning of the function:

if ($N < 1) {
   my @retvals = ([]);
   return sub { shift @retvals };
}

Now on with the more interesting, general case. Taking inspiration from our recursive implementation, we keep a $first variable holding the beginning of the list, and some way to track the rest. We will still leverage a recursive implementation, only this time the recursion will get us a sub-iterator that we place in variable $rit.

As we already saw in other posts (e.g. Loop from iterator, Iterator-based implementation of Permutations) that a generic strategy is to have a loop and then a return from within the loop, while keeping the state in closed-upon variables. Our variables are exactly $first and $rit, so we “just” have to set the loop:

return sub {
   my @retval;
   while ($first > 0) {
      $rit //= int_sums_iterator($N - $first, $first);
      if (my $rest = $rit->()) {
         return [$first, $rest->@*];
      }
      ($first, $rit) = ($first - 1, undef);
   }
   return;
}

We iterate for decreasing values of $first, until we hit the rock bottom. If we exit from the loop because $first went down to 0, we just return, flagging the end of our iterator; otherwise:

• we make sure that $rit contains an iterator to the sub sequences of whatever comes after $first;
• we extract the next sub-sequence and, if valid, use it to build the return value.

As we can see, we leverage int_sums_iterator recursively to get the sub-iterator we are looking after. We might do differently (e.g. building up an explicit stack) - maybe we will take a look at it in the future.

So… here we are, with a mixed recursive/iterator based approach that allows us to avoid pre-computing all elements up-front:

#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;

sub int_sums_iterator ($N, $max = undef) {
   if ($N < 1) {
      my @retvals = ([]);
      return sub { shift @retvals };
   }
   $max //= $N;
   my $first = $N < $max ? $N : $max;
   my $rit   = undef;
   return sub {
      my @retval;
      while ($first > 0) {
         $rit //= int_sums_iterator($N - $first, $first);
         if (my $rest = $rit->()) {
            return [$first, $rest->@*];
         }
         ($first, $rit) = ($first - 1, undef);
      }
      return;
   }
}

my $it = int_sums_iterator(shift || 3);
my $n = 4;
while ((my $list = $it->()) && ($n > 0)) {
   say "($list->@*)";
   --$n;
}

As we see, we decided to cut the output at the fourth sequence:

$ perl int-sums.pl 6
(6)
(5 1)
(4 2)
(4 1 1)

I guess it’s everything for this post!