TL;DR

Well, moving on in this series…

Previous post All partitions of a set into same-sized subsets set the base for doing the partitioning of a set of items into subsets with the same size, making sure to only include different arrangements.

With this in our pocket, we can now proceed to generate all possible partitions following a pre-definite scheme. An example of such a scheme would be to partition set:

into two $3$-sized subsets and two $2$-sized subsets.

Does this ring a bell? It’s like we’re saying that our starting set has $10$ items, and we would like to partition it according to the following partition of the integer $10$:

Take a look at previous post All positive integer sums, as iterator for a refresher, if you don’t know what I’m talking about!

OK, let’s then move on with an implementation of a Perl function that provides an iterator for all possible partitions according to the provided scheme:

sub differsets_partition_iterator ($sizs, @items) {
   my ($fs, @sizes) = $sizs->@*;
   return equalsets_partition_iterator($fs->[1], @items)
      if @sizes == 0;
   my $cit = combinations_iterator($fs->[0] * $fs->[1], @items);
   my ($leader_it, $rest_it);
   my @leader;
   my $rref; # "rest" after leader
   return sub {
      return unless $cit;
      while ('necessary') {
         $leader_it //= do {
            (my $lref, $rref) = $cit->() or do {
               $cit = undef;
               return;
            };
            equalsets_partition_iterator($fs->[1], $lref->@*);
         };
         $rest_it //= do {
            @leader = $leader_it->() or do {
               $leader_it = undef;
               redo;
            };
            differsets_partition_iterator(\@sizes, $rref->@*);
         };
         my @sequence = $rest_it->() or do {
            $rest_it = undef;
            redo;
         };
         return (@leader, @sequence);
      }
   };
}

The name is… far from being catchy. Whatever, Stat rosa pristina nomine, nomina nuda tenemus.

We receive the scheme as an array reference $sizs, filled with array references that each carry two integer values, i.e. a count and a size. In other terms, exactly one of the possible outputs from what we described in All positive integer sums, as iterator. The rest of the inputs is the list of items in our set.

The idea is to adopt a divide et impera approach: take the first pair and generate all combinations of the combined size, and recurse with the rest.

Well, let’s see an example. Suppose that we want to do the partitioning in the example above: $10$ items, partitioned as two $3$-sized and two $2$-sized subsets.

The two sets with three items inside have to be treated like we described in the previous post, because they share the same size. To do this, we can:

• first generate all possible combinations of $6$ elements out of the available $10$, i.e. getting as many items as will be needed to fill the two $3$-sized subsets exactly;
• then apply the reasoning to the rest of $4$ items from each combinations, fitting them into $2$-sized subsets.

The ending condition for the recursion is when we are left with only one pair in the scheme: in this case, we can just hand over to equalsets_partition_iterator and call it a day. This is why we check for this condition at the beginning of the function.

Inside the main iterator, though, we have to keep track of two different levels of iteration:

• the external one, where we iterate through all possible sequences generated by the leader (in our example, it would be all possible partitions of a specific combination of $6$ items into two subsets containing $3$ items each);
• the internal one, where we keep the @leader fixed, and iterate through what the recursion provides us (in our example, this means iterating through all partitions of a specific subset of $4$ elements left from the $6$-combination drawn for generating the leaders).

This is why we keep two iterators $leader_it and $rest_it. Pretty complicated, uh?

The result is encouraging though:

{ {a b c}, {d e f}, {g h}, {i l} }
{ {a b c}, {d e f}, {g i}, {h l} }
... 6296 items in between...
{ {e i l}, {f g h}, {a c}, {b d} }
{ {e i l}, {f g h}, {a d}, {b c} }

Is $6300$ the number of partitions of this kind we were expecting? Let’s see…

Now we’re ready for the big prize: generating all distinct partitions of a set! Let’s just wait for the next post… 😄