:github_url: https://github.com/svenevs/exhale-companion


.. _program_listing_file_ckpttncpp_set_partition.hpp:

Program Listing for File set_partition.hpp
==========================================

|exhale_lsh| :ref:`Return to documentation for file <file_ckpttncpp_set_partition.hpp>` (``ckpttncpp/set_partition.hpp``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   #pragma once
   
   #include <type_traits>
   
   template <int N, int K>
   constexpr auto Stirling2nd()
   {
       if constexpr (K >= N || K <= 1)
       {
           return std::integral_constant<int, 1> {};
       }
       else
       {
           return std::integral_constant<int,
               Stirling2nd<N - 1, K - 1>() + K * Stirling2nd<N - 1, K>()> {};
       }
   }
   
   // Set Partition
   //
   // A set partition of the set [n] = {1,2,3,...,n} is a collection B0,
   // B1, ... Bj of disjoint subsets of [n] whose union is [n]. Each Bj
   // is called a block. Below we show the partitions of [4]. The periods
   // separtate the individual sets so that, for example, 1.23.4 is the
   // partition {{1},{2,3},{4}}.
   //   1 block:  1234
   //   2 blocks: 123.4   124.3   134.2   1.234   12.34   13.24   14.23
   //   3 blocks: 1.2.34  1.24.3  14.2.3  13.2.4  12.3.4
   //   4 blocks: 1.2.3.4
   //
   // Each partition above has its blocks listed in increasing order of
   // smallest element; thus block 0 contains element 1, block1 contains
   // the smallest element not in block 0, and so on. A Restricted Growth
   // string (or RG string) is a sring a[1..n] where a[i] is the block in
   // whcih element i occurs. Restricted Growth strings are often called
   // restricted growth functions. Here are the RG strings corresponding
   // to the partitions shown above.
   //
   //   1 block:  0000
   //   2 blocks: 0001, 0010, 0100, 0111, 0011, 0101, 0110
   //   3 blocks: 0122, 0121, 0112, 0120, 0102,
   //
   // ...more
   //
   // Reference:
   // Frank Ruskey. Simple combinatorial Gray codes constructed by
   // reversing sublists. Lecture Notes in Computer Science, #762,
   // 201-208. Also downloadable from
   // http://webhome.cs.uvic.ca/~ruskey/Publications/SimpleGray/SimpleGray.html
   //
   #include <boost/coroutine2/all.hpp>
   #include <cassert>
   #include <cctype>
   #include <cstdio>
   #include <functional>
   #include <utility>
   
   class set_partition_
   {
       using ret_t = std::tuple<int, int>;
       using Fun = std::function<void(ret_t)>;
   
     private:
       // int b[100 + 1]; /* maximum value of n */
       // int cnt{};
       Fun yield;
   
     public:
       explicit set_partition_(Fun yield_)
           : yield(std::move(yield_))
       {
       }
   
       void run(int n, int k)
       {
           if (k % 2 == 0)
           {
               this->_GEN0_even(n, k);
           }
           else
           {
               this->_GEN0_odd(n, k);
           }
       }
   
     private:
       void _Move(int x, int y)
       {
           yield(std::tuple {x, y});
       }
   
       void _GEN0_even(int n, int k);
   
       void _NEG0_even(int n, int k);
   
       void _GEN1_even(int n, int k);
   
       void _NEG1_even(int n, int k);
   
       void _GEN0_odd(int n, int k);
   
       void _NEG0_odd(int n, int k);
   
       void _GEN1_odd(int n, int k);
   
       void _NEG1_odd(int n, int k);
   };
   
   using ret_t = std::tuple<int, int>;
   using coro_t = boost::coroutines2::coroutine<ret_t>;
   
   extern coro_t::pull_type set_partition(int n, int k);