All partitions of a set

TL;DR

At the very last, we can generate all partitions of a set.

In last post All partitions of a set into differently arranged subsets we got our last piece that separates us from generating all partitions of a set.

Function differsets_partition_iterator takes a specific decomposition of an integer $N$ and a list of $N$ items, providing us back all possible partitions according to that specific decomposition.

Now we are ready to integrate this with the function we saw in All positive integer sums, as iterator and create an iterator to reach our initial goal.

Let’s get to the code:

sub all_partitions_iterator (@items) {
   my $sit = compactify(int_sums_iterator(scalar @items));
   my $ssit;
   return sub {
      while ('necessary') {
         $ssit //= do {
            my $arrangement = $sit->() or return;
            differsets_partition_iterator($arrangement, @items);
         };
         my @sequence = $ssit->() or do {
            $ssit = undef;
            redo;
         };
         return @sequence;
      }
   }
}

It’s probably sort-of anticlimax:

we create the $sit iterator to go through all possible decomposition of the number $N$ of items in @items;
for each of those decomposition, we create an iterator and use it until it’s exhausted and we need to move on to the next decomposition.

So… it is working?!? Let’s see for the first values (considering only non-empty sets):

--- 1 item only
{ {a} }

--- 2 items
{ {a b} }
{ {a}, {b} }

--- 3 items
{ {a b c} }
{ {a b}, {c} }
{ {a c}, {b} }
{ {b c}, {a} }
{ {a}, {b}, {c} }

--- you get the idea
{ {a b c d} }
{ {a b c}, {d} }
{ {a b d}, {c} }
   ...
{ {b d}, {a}, {c} }
{ {c d}, {a}, {b} }
{ {a}, {b}, {c}, {d} }

---
{ {a b c d e} }
{ {a b c d}, {e} }
{ {a b c e}, {d} }
   ...
{ {c e}, {a}, {b}, {d} }
{ {d e}, {a}, {b}, {c} }
{ {a}, {b}, {c}, {d}, {e} }

---
{ {a b c d e f} }
{ {a b c d e}, {f} }
{ {a b c d f}, {e} }
   ...
{ {d f}, {a}, {b}, {c}, {e} }
{ {e f}, {a}, {b}, {c}, {d} }
{ {a}, {b}, {c}, {d}, {e}, {f} }

---
{ {a b c d e f g} }
{ {a b c d e f}, {g} }
{ {a b c d e g}, {f} }
   ...
{ {e g}, {a}, {b}, {c}, {d}, {f} }
{ {f g}, {a}, {b}, {c}, {d}, {e} }
{ {a}, {b}, {c}, {d}, {e}, {f}, {g} }

---
{ {a b c d e f g h} }
{ {a b c d e f g}, {h} }
{ {a b c d e f h}, {g} }
   ...
{ {f h}, {a}, {b}, {c}, {d}, {e}, {g} }
{ {g h}, {a}, {b}, {c}, {d}, {e}, {f} }
{ {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h} }

---
{ {a b c d e f g h i} }
{ {a b c d e f g h}, {i} }
{ {a b c d e f g i}, {h} }
   ...
{ {g i}, {a}, {b}, {c}, {d}, {e}, {f}, {h} }
{ {h i}, {a}, {b}, {c}, {d}, {e}, {f}, {g} }
{ {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i} }

---
{ {a b c d e f g h i j} }
{ {a b c d e f g h i}, {j} }
{ {a b c d e f g h j}, {i} }
   ...
115973	{ {h j}, {a}, {b}, {c}, {d}, {e}, {f}, {g}, {i} }
115974	{ {i j}, {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h} }
115975	{ {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i}, {j} }

The number of partitions is correct so I’d say that it’s working fine. Until a bug comes out, at least.

If you’re interested into looking at the full code, there is a local copy here.

One last thing! We can now solve challenge PWC108 - Bell Numbers in a different way:

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

sub bell_number ($N) {
   return 1 unless $N;  # that pesky empty-set case...
   my $it = all_partitions_iterator(1 .. $N);
   my $n = 0;
   ++$n while $it->();
   return $n;
}

printf "B%d: %d\n", $_, bell_number($_) for 0 .. 9;
exit 0;

# ... put the rest of the code here...

Stay safe folks!

ETOOBUSY 🚀 minimal blogging for the impatient