Generating set partitions – replacing virtual functions with protected inheritance

The purpose of this long post is twofold: first, I really am in need of an efficiently implemented set partition enumerating library, and second, I would like to use this work as a pretext to share and discuss the designs that I considered. The latter is the main part here, as the algorithms themselves are taken from other people’s work, and the c++ discussion does not require a thorough understanding of them.

A set partition is a way to split elements of a finite set into disjoint subsets, called blocks. A way to model it is to take the set of natural numbers {0,1,2,…,n} as the initial set, and give each member a block number. Thus, for n=4 the partition (0,1,0,1) defines two blocks, block 0 containing elements 0 and 2, and block 1 containing elements 1 and 3. Of course, had we taken partition (1,0,1,0), we would have got the same split, so to avoid repetition there has to be a normalization rule: we start with block 0, and if a new block is needed, it gets the next number unused so far. A nice overview of the algorithms that accomplish this task has been gathered by Michael Orlov (section Technical reports at https://www.cs.bgu.ac.il/~orlovm/papers/ ), there’s even an accompanying implementation, but I think that with modern c++ one can now do better. And I need it for a student of mine who is doing research on some industrial process optimisation as well as for purely mathematical research, set partitions have a lot to do with probability, see for instance the explanatory paper by Roland Speicher: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.9723

1. Elementary solution for all partitions


Partitions of fixed size can be looked upon as an ordered collection of immutable elements, and the most natural way to implement this kind of objects in c++ is to have a collection object equipped with iterators, technically speaking const_iterators. Actually, most work is done in iterators in this case, the collection object is just needed for the convenience of having begin and end methods, which allows for instance the range for loop syntax. Michael Orlov’s paper details four algorithms: initialization of first and last partition and generation of next and previous partition, in terms of two sequences, a current partition k and a running maximum of used block numbers m. I will not analyse the algorithms themselves, it is not necessary for the c++ discussion that follows, and Michael has already done a prefect job, please consult his text. So, my first take at implementing the unrestricted set partitions is as follows:

namespace ljwo
  {
  namespace partitions_straight
    {
    typedef std::vector<int> partition;

    class all
      {
        int size_;
      public:
        all(int dim)
          : size_(dim)
          {
          assert(dim>0);
          }
        auto size(void) const -> int
          {
          return size_;
          }

        class const_iterator 
            : public std::iterator<std::bidirectional_iterator_tag
                                  ,const partition
                                  >
          {
            bool end_;
            std::vector<int> k_;
            std::vector<int> m_;
          public:
            const_iterator(void)
              : end_(true)
              {}
            const_iterator(int dim, bool end=false)
              : end_(end),
                k_(dim,0),
                m_(dim,0)
              {
              assert(dim > 0);
              }
            auto initialize_last(void) -> void
              {
              std::iota(std::begin(k_),std::end(k_),0);
              std::iota(std::begin(m_),std::end(m_),0);
              }
            auto operator*(void) const -> reference
              {
              return k_;
              }
            auto operator->(void) const -> pointer
              {
              return &k_;
              }
            auto operator++(void) -> const_iterator&
              {
              if(!end_)
                {
                int n = k_.size();
                bool not_found = true;
                for(int i=n-1; i>0; --i)
                  if(k_[i]<=m_[i-1])
                    {
                    ++(k_[i]);
                    m_[i]=std::max(m_[i],k_[i]);
                    for(int j=i+1; j<n; ++j)
                      {
                      k_[j]=k_[0];
                      m_[j]=m_[i];
                      }
                    not_found = false;
                    break;
                    }
                end_=not_found;
                }
              return *this;
              }
            auto operator++(int) -> const_iterator
              {
              const_iterator ret = *this;
              ++(*this);
              return ret;
              }
            auto operator--(void) -> const_iterator&
              {
              if(end_)
                {
                end_=false;
                initialize_last();
                }
              else
                {
                int n = k_.size();
                for(int i=n-1; i>0; --i)
                  if(k_[i]>k_[0])
                  // undefined behaviour if going before first
                    {
                    --(k_[i]);
                    m_[i]=m_[i-1];
                    for(int j=i+1; j<n; ++j)
                      {
                      m_[j]=m_[i]+j-i;
                      k_[j]=m_[j];
                      }
                    break;
                    }
                }
              return *this;
              }
            auto operator--(int) -> const_iterator
              {
              const_iterator ret = (*this);
              --(*this);
              return ret;
              }
            auto operator==(const const_iterator& ci) const -> bool
              {
              return (end_==ci.end_) && (end_ || (k_==ci.k_ && m_==ci.m_));
              }
            auto operator!=(const const_iterator& ci) const -> bool
              {
              return !((*this)==ci);
              }
          };
        auto begin(void) const -> const_iterator
          {
          return const_iterator(size());
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator(size(),true);
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),true));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size()));
          }
      }; // class all
    } // namespace partitions_straight
  } // namespace ljwo

I need to say that I like the new function syntax of c++11 much better than the old one, because it ressembles the mathematical notation f : D→R, so I tend to use it everywhere, and believe it is the way to go. In the code above I used the four algorithms defining the problem either inside the appropriate functions, or as separate named functions. There is, however, one thing that does not appear in the original paper, and this is the infrastructure for past-the-end iterators. The standard requires two things from bidirectional iterators: first, that it be possible to increment an iterator past the last actual element of a collection, use it for comparison with other iterators, and possibly decrement it back to dereferenceable range, and second, to default–construct an iterator that will compare equal to any other past-the-end iterator of the same type.

For testing purposes I am going to use a template, to be able to plug different solutions to the same test:

    template<class Partitions>
auto test_partitions(int repeat = 1) -> double
  {
  static const int bell_numbers[] {1,1,2,5,15,52,203,877,4140,
                                   21147,115975,678570,4213597};
  auto start = std::chrono::system_clock::now();
  for(int j=0; j<repeat; ++j)
    for(int i=1; i<13; ++i)
      {
      int c=0;
      Partitions ps(i);
      for(auto& p : ps)
        ++c;
      assert(c==bell_numbers[i]);
      }
  return (std::chrono::system_clock::now()-start).count();
  }

auto main(void) -> int
  {
  std::cout << "ljwo::paritions_straight test time: " 
            << test_partitions<ljwo::partitions_straight::all>() 
            << "\n";
  }

This is not a comprehensive test, it only checks the total number of partitions of a given size (a.k.a. Bell numbers), but it is unlikely that a wrong algorithm would produce a sequence of the right length. You are free to replace assert by a testing macro of your favourite testing suite. I am also going to use this test to assess efficiency, so it reports its running time. And, if we were interested in just generating all partitions of a set, we could live by that code. Unfortunately, or fortunately, that student of mine has a fixed number of teams to which he has to attribute sites, fixed number of teams in this case translates to set partitions with a fixed number of blocks.

2. Generalizing to partitions with fixed number of blocks


2.1 Public inheritance and virtual functions solution


There are four customization points in the code above, they correspond to the four algorithms of Michael’s paper. If we need fixed number of blocks partitions, we need to substitute the plain for the restricted ones. The past-the-end and interface-to-algorithm mechanics are the same in both cases. They teach us in object-oriented programming courses that this is an opportunity for code reuse with inheritance and virtual functions, so let me try to explore that idea. We will need a base class for the iterators, with the four algorithms specified as virtual functions. A naive implementation does not work, let me show an incomplete listing from beginning until the problem:

namespace ljwo
  {
  namespace partitions_naive
    {
    typedef std::vector<int> partition;

    class const_iterator_base 
        : public std::iterator<std::bidirectional_iterator_tag,const partition>
      {
      protected:
        bool end_;
        std::vector<int> k_;
        std::vector<int> m_;
      public:
        const_iterator_base(void)
          : end_(true)
          {}
        const_iterator_base(int dim, bool end=false)
          : end_(end),
            k_(dim),
            m_(dim)
          {
          initialize_first(); // not a virtual call
          }
        virtual ~const_iterator_base(void) {}
        virtual auto initialize_first(void) -> void = 0;
        virtual auto initialize_last(void) -> void = 0;
        virtual auto next_partition(void) -> bool = 0;
        virtual auto previous_partition(void) -> void = 0;

        auto operator*(void) const -> reference
          {
          return k_;
          }
        auto operator->(void) const -> pointer
          {
          return &k_;
          }
        auto operator++(void) -> const_iterator_base&
          {
          if(!end_)
            {
            end_=!next_partition();
            }
          return *this;
          }
        auto operator++(int) -> const_iterator_base
        //error: invalid abstract return type for member function
          {
          const_iterator_base ret = *this;
          ++(*this);
          return ret;
          }

There is not enough type information here to produce a meaningful result of suffix operator ++, but that can be helped, CRTP to the rescue:

namespace ljwo
  {
  namespace partitions_virtual
    {
    typedef std::vector<int> partition;

        template<class const_iterator>
    class const_iterator_base 
        : public std::iterator<std::bidirectional_iterator_tag,const partition>
      {
      protected:
        bool end_;
        std::vector<int> k_;
        std::vector<int> m_;
      public:
        const_iterator_base(void)
          : end_(true)
          {}
        const_iterator_base(int dim, bool end=false)
          : end_(end),
            k_(dim),
            m_(dim)
          {
          //initialize_first(); // not a virtual call
          //if uncommented undefined reference to 
          //ljwo::partitions_virtual::const_iterator_base
          //  <ljwo::partitions_virtual::const_iterator
          //  >::initialize_first
          //Making use of "using" in two classes below impossible
          }
        virtual ~const_iterator_base(void) {}
        virtual auto initialize_first(void) -> void = 0;
        virtual auto initialize_last(void) -> void = 0;
        virtual auto next_partition(void) -> bool = 0;
        virtual auto previous_partition(void) -> void = 0;

        auto operator*(void) const -> reference
          {
          return k_;
          }
        auto operator->(void) const -> pointer
          {
          return &k_;
          }
        auto operator++(void) -> const_iterator&
          {
          if(!end_)
            {
            end_=!next_partition();
            }
          return static_cast<const_iterator&>(*this);
          }
        auto operator++(int) -> const_iterator
          {
          const_iterator ret = *this;
          ++(*this);
          return ret;
          }
        auto operator--(void) -> const_iterator&
          {
          if(end_)
            {
            end_=false;
            initialize_last();
            }
          else
            {
            previous_partition();
            }
          return static_cast<const_iterator&>(*this);
          }
        auto operator--(int) -> const_iterator
          {
          const_iterator ret = (*this);
          --(*this);
          return ret;
          }
        auto operator==(const const_iterator& ci) const -> bool
          {
          return (end_==ci.end_) && (end_ || (k_==ci.k_ && m_==ci.m_));
          }
        auto operator!=(const const_iterator& ci) const -> bool
          {
          return !((*this)==ci);
          }
      };

    class all
      {
        int size_;
      public:
        all(int size)
          : size_(size)
          {
          assert(size>0);
          }
        auto size(void) const -> int
          {
          return size_;
          }
        class const_iterator : public const_iterator_base<const_iterator>
          {
          public:
            //using const_iterator_base::const_iterator_base;
            const_iterator(int dim, bool end=false)
              : const_iterator_base<const_iterator>(dim,end)
              {
              initialize_first();
              }
            auto initialize_first(void) -> void override
              {
              std::fill(std::begin(k_),std::end(k_),0);
              std::fill(std::begin(m_),std::end(m_),0);
              }
            auto initialize_last(void) -> void override
              {
              std::iota(std::begin(k_),std::end(k_),0);
              std::iota(std::begin(m_),std::end(m_),0);
              }
            auto next_partition(void) -> bool override
              {
              int n = k_.size();
              bool next_found = false;
              for(int i=n-1; i>0; --i)
                if(k_[i]<=m_[i-1])
                  {
                  ++(k_[i]);
                  m_[i]=std::max(m_[i],k_[i]);
                  for(int j=i+1; j<n; ++j)
                    {
                    k_[j]=k_[0];
                    m_[j]=m_[i];
                    }
                  next_found = true;
                  break;
                  }
              return next_found;
              }
            auto previous_partition(void) -> void override
              {
              int n = k_.size();
              for(int i=n-1; i>0; --i)
                if(k_[i]>k_[0])
                // undefined behaviour if going before first
                  {
                  --(k_[i]);
                  m_[i]=m_[i-1];
                  for(int j=i+1; j<n; ++j)
                    {
                    m_[j]=m_[i]+j-i;
                    k_[j]=m_[j];
                    }
                  break;
                  }
              }
          }; // class const_iterator
        auto begin(void) const -> const_iterator
          {
          return const_iterator(size());
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator{size(),true};
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),true));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size()));
          }
      }; // class all
    //////////////////////////////////////////////////////////////////////
    class kblocks
      {
        int size_;
        int blocks_;
      public:
        kblocks(int dim, int blocks)
          : size_(dim),
            blocks_(blocks)
          {
          assert(dim>0);
          assert(blocks>0);
          assert(blocks<=dim);
          }
        auto size(void) const -> int
          {
          return size_;
          }
        auto blocks(void) const -> int
          {
          return blocks_;
          }
        class const_iterator : public const_iterator_base<const_iterator>
          {
            int blocks_;
          public:
            //using const_iterator_base::const_iterator_base;
            const_iterator(int dim, int blocks, bool end=false)
              : const_iterator_base<const_iterator>(dim,end),
                blocks_(blocks)
              {
              initialize_first();
              }
            auto initialize_first(void) -> void override
              {
              std::fill(std::begin(k_),std::end(k_)-blocks_,0);
              std::fill(std::begin(m_),std::end(m_)-blocks_,0);
              std::iota(std::end(k_)-blocks_,std::end(k_),0);
              std::iota(std::end(m_)-blocks_,std::end(m_),0);
              }
            auto initialize_last(void) -> void override
              {
              std::iota(std::begin(k_),std::begin(k_)+blocks_,0);
              std::iota(std::begin(m_),std::begin(m_)+blocks_,0);
              int last = *(std::begin(k_)+blocks_-1);
              std::fill(std::begin(k_)+blocks_,std::end(k_),last);
              std::fill(std::begin(m_)+blocks_,std::end(m_),last);
              }
            auto next_partition(void) -> bool override
              {
              int n = k_.size();
              bool next_found = false;
              for(int i=n-1; i>0; --i)
                if((k_[i]<blocks_-1) && (k_[i]<=m_[i-1]))
                  {
                  ++(k_[i]);
                  m_[i]=std::max(m_[i],k_[i]);
                  for(int j=i+1; j<=n-(blocks_-m_[i]); ++j)
                    {
                    k_[j]=0;
                    m_[j]=m_[i];
                    }
                  for(int j=n-(blocks_-m_[i])+1; j<n; ++j)
                    {
                    m_[j]=blocks_-(n-j);
                    k_[j]=m_[j];
                    }
                  next_found = true;
                  break;
                  }
              return next_found;
              }
            auto previous_partition(void) -> void override
              {
              int n = k_.size();
              for(int i=n-1; i>0; --i)
                if((k_[i]>0) && (blocks_-m_[i-1]<=n-i))
                // undefined behaviour if going before first
                  {
                  --(k_[i]);
                  m_[i]=m_[i-1];
                  for(int j=i+1; j<=i+(blocks_-m_[i])-1; ++j)
                    {
                    m_[j]=m_[i]+j-i;
                    k_[j]=m_[j];
                    }
                  for(int j=i+(blocks_-m_[i]); j<n; ++j)
                    {
                    m_[j]=blocks_-1;
                    k_[j]=m_[j];
                    }
                  break;
                  }
              }
          }; // class const_iterator

        auto begin(void) const -> const_iterator
          {
          return const_iterator(size(),blocks());
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator{size(),blocks(),true};
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),blocks(),true));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),blocks()));
          }
      }; // class kblocks
    } // namespace partitions_virtual
  } // namespace ljwo

This works, all partitions pass the test mentionned before, in Listing 1, kblocks partitions pass another:

    template<class Partitions>
auto test_kblocks_partitions(int repeat = 1) -> double
  {
  // stirling numbers S(i,i-5) for i=5,6,...,14
  static const int stirling_numbers[] {0, 1, 63, 966, 7770, 42525, 179487, 
                                       627396, 1899612, 5135130};
  auto start = std::chrono::system_clock::now();
  for(int j=0; j<repeat; ++j)
    for(int i=6; i<15; ++i)
      {
      int c=0;
      Partitions ps(i,i-5);
      for(auto& p : ps)
        ++c;
      assert(c==stirling_numbers[i-5]);
      }
  return (std::chrono::system_clock::now()-start).count();
  }

That test counts partitions of sets with 6,7,…,14 elements into 1,2,…,9 blocks, respectively, and compares the count to Stirling numbers calculated courtesy of WolframAlpha.

Work it does, but, alas, there are serious problems with this code. First, as already commented in the listing, the generation of the first partition does not work like the other customisation points, since a function call from a constructor is not virtually bound, it is always resolved inside the class of the constructor. That means that we cannot uncomment the commented–out using clauses for constructors, because there’s nontrivial work that needs to be done in constructors of the iterator classes implementing the particular solutions. Second, the base class is visible to everybody, and the inheritance is public, despite that it is an implementation detail and nobody’s business save the author or maintainer. Public inheritance entails incentive to throw in a virtual destructor into the base class, Third, the primary purpose of inheritance and virtual functions is to allow a runtime selection of the type of a pointed-to object. Now, in our scenario such things do not happen, once we have an all::const_iterator or a kblocks::const_iterator, it is there to stay until not needed anymore. And fourth, performance has to be considered. The following test

auto test1(void) -> void
  {
  double s1=0.0;
  double s3=0.0;
  const int repeat = 50;
  for(int i=0; i<10; ++i)
    {
    s1 += test_partitions<ljwo::partitions_straight::all>(repeat);
    s3 += test_partitions<ljwo::partitions_virtual::all>(repeat);
    }
  std::cout << "ljwo::partitions_straight::all test time: " << s1 << "\n";
  std::cout << "ljwo::partitions_virtual::all  test time: " << s3 << "\n";
  }

built with -std=c++11 -O3 -march=native on all of my machines with gcc 4.8.1 or 4.9.2 and clang 3.5.0 typically gives a 40-50% higher figure for this design than for the previous partitions_straight solution. However, there are surprises in measurments, I discuss them below, after I consider all the designs. Those differences may or may not matter to you, depending on how expensive is the calculation that you want to do for each partition, I am just incrementing an int which takes little time, but the penalty adds to the picture. There has to be a better way of doing this, and I don’t mean copy–paste with change of algorithms, DRY, Don’t Repeat Yourself.

2.2. Policy–based solutions


It is well known that design using policy classes has, in some ways, complementary advantages and disadvantages to inheritance. The general idea is to package the custom sets of functions into classes that are then passed as template parameter to a solution class. That solution class then inherits privately from the template parameter. Comparing this structure to the one of the previous section, there’s an inverse of logic, as the custom functions are in base classes as opposed to derived classes. The classical reference for that subject is the book Modern C++ Design by Andrei Alexandrescu. There is one difficulty in our problem at hand, though, that is not well covered by examples of that book. Our customisation points operate on data, and it is the same data that is needed in the solution class for implementation of the interface. That data has to live somewhere, in one or more of the classes. There are roughly three possibilities here, and I will discuss all of them. The data, excluding the fixed number of blocks that is specific to one policy but not the other, can live in the solution class, or can live in the policy classes, or can live in a common base class of the policy classes.

2.2.1. Data in policy classes


This option is not really viable, as it would require us to repeat common data definitions in many policy classes, and, as you know, DRY, Don’t Repeat Yourself.

2.2.2. Data in solution class


This case has two subsolutions. In one of them, we will try to keep the signatures of the custom functions, that is keep the arguments’ lists (void). That leads to code of which the following listing is a sample:

    template<class Actual>
class policy
  {
  public:
    auto previous_partition(void) -> void
      {
      int n = static_cast<Actual*>(this)->k_.size();
      }
  };

    template<template <class> class Policy>
class const_iterator_base : private Policy<const_iterator_base<Policy>>
  {
    std::vector<int> k_;
    friend class Policy<const_iterator_base<Policy>>;
  public:
    auto run(void) -> void
      {
      Policy<const_iterator_base<Policy>>::previous_partition();
      }
  };

As you see, to let the policy base class use solution’s private data we need to make it friend, and we need to let it know the precise type of the solution class through CRTP. Since the solution class depends on the policy class, that results in the Policy<const_iterator_base<Policy>> monstrosity. Moreover, every access to anything has to be qualified with an ugly cast as in static_cast<Actual*>(this)->k_.size(). No chance for a nice using clause here. Although this can be carried further to a complete solution, let me not pursue this path.

The second subsolution consists in changing signatures of the custom functions so that they get data required to operate by reference. That gets us to a complete solution partitions_stateless:

namespace ljwo
  {
  namespace detail
    {
    enum class enabler {};
    }
      template <typename Condition>
  using EnableIf = typename std::enable_if
                              <
                              Condition::value, 
                              detail::enabler
                              >::type;

  namespace partitions_stateless
    {
    typedef std::vector<int> partition;

    class const_iterator_all
      {
      protected:
        const_iterator_all(void)
          {}
        using constructor_args = std::tuple<>;
        auto initialize_first(partition& k_, partition& m_, bool& end_) -> void
          {
          std::fill(std::begin(k_),std::end(k_),0);
          std::fill(std::begin(m_),std::end(m_),0);
          }
        auto initialize_last(partition& k_, partition& m_, bool& end_) -> void
          {
          std::iota(std::begin(k_),std::end(k_),0);
          std::iota(std::begin(m_),std::end(m_),0);
          }
        auto next_partition(partition& k_, partition& m_, bool& end_) -> bool
          {
          int n = k_.size();
          bool not_found = true;
          for(int i=n-1; i>0; --i)
            if(k_[i]<=m_[i-1])
              {
              ++(k_[i]);
              m_[i]=std::max(m_[i],k_[i]);
              for(int j=i+1; j<n; ++j)
                {
                k_[j]=k_[0];
                m_[j]=m_[i];
                }
              not_found = false;
              break;
              }
          return not_found;
          }
        auto previous_partition(partition& k_, partition& m_, bool& end_) -> void
          {
          int n = k_.size();
          for(int i=n-1; i>0; --i)
            if(k_[i]>k_[0])
            // undefined behaviour if going before first
              {
              --(k_[i]);
              m_[i]=m_[i-1];
              for(int j=i+1; j<n; ++j)
                {
                m_[j]=m_[i]+j-i;
                k_[j]=m_[j];
                }
              break;
              }
          }
      }; // class const_iterator_all

    class const_iterator_kblocks
      {
        int blocks_;
      protected:
        const_iterator_kblocks(void)
          : blocks_(0)
          {}
        using constructor_args = std::tuple<int>;
        const_iterator_kblocks(int blocks)
          : blocks_(blocks)
          {
          assert(blocks>0);
          //assert(blocks<=dim);  // no way to assert on that, 
                                  // unless constructor given dim
          }
        auto initialize_first(partition& k_, partition& m_, bool& end_) -> void
          {
          std::fill(std::begin(k_),std::end(k_)-blocks_,0);
          std::fill(std::begin(m_),std::end(m_)-blocks_,0);
          std::iota(std::end(k_)-blocks_,std::end(k_),0);
          std::iota(std::end(m_)-blocks_,std::end(m_),0);
          }
        auto initialize_last(partition& k_, partition& m_, bool& end_) -> void
          {
          std::iota(std::begin(k_),std::begin(k_)+blocks_,0);
          std::iota(std::begin(m_),std::begin(m_)+blocks_,0);
          int last = *(std::begin(k_)+blocks_-1);
          std::fill(std::begin(k_)+blocks_,std::end(k_),last);
          std::fill(std::begin(m_)+blocks_,std::end(m_),last);
          }
        auto next_partition(partition& k_, partition& m_, bool& end_) -> bool
          {
          int n = k_.size();
          bool not_found = true;
          for(int i=n-1; i>0; --i)
            if((k_[i]<blocks_-1) && (k_[i]<=m_[i-1]))
              {
              ++(k_[i]);
              m_[i]=std::max(m_[i],k_[i]);
              for(int j=i+1; j<=n-(blocks_-m_[i]); ++j)
                {
                k_[j]=0;
                m_[j]=m_[i];
                }
              for(int j=n-(blocks_-m_[i])+1; j<n; ++j)
                {
                m_[j]=blocks_-(n-j);
                k_[j]=m_[j];
                }
              not_found = false;
              break;
              }
          return not_found;
          }
        auto previous_partition(partition& k_, partition& m_, bool& end_) -> void
          {
          int n = k_.size();
          for(int i=n-1; i>0; --i)
            if((k_[i]>0) && (blocks_-m_[i-1]<=n-i))
            // undefined behaviour if going before first
              {
              --(k_[i]);
              m_[i]=m_[i-1];
              for(int j=i+1; j<=i+(blocks_-m_[i])-1; ++j)
                {
                m_[j]=m_[i]+j-i;
                k_[j]=m_[j];
                }
              for(int j=i+(blocks_-m_[i]); j<n; ++j)
                {
                m_[j]=blocks_-1;
                k_[j]=m_[j];
                }
              break;
              }
          }
      }; // class const_iterator_kblocks

        template<class const_iterator_spec>
    class const_iterator_base : public std::iterator
                                         <
                                         std::bidirectional_iterator_tag,
                                         const partition
                                         >,
                                private const_iterator_spec
      {
        bool end_;
        std::vector<int> k_;
        std::vector<int> m_;
      public:
        using const_iterator_spec::initialize_first;
        using const_iterator_spec::initialize_last;
        using const_iterator_spec::next_partition;
        using const_iterator_spec::previous_partition;

        const_iterator_base(void)
          : end_(true)
          {}

            template<class... Args,
                     EnableIf
                       <
                       std::is_same
                         <
                         std::tuple<Args...>,
                         typename const_iterator_spec::constructor_args
                         >
                       >...
                    >
        const_iterator_base(int dim, bool end, Args... args)
          : const_iterator_spec(std::forward<Args>(args)...),
            end_(end),
            k_(dim),
            m_(dim)
          {
          assert(dim>0);
          initialize_first(k_,m_,end_);
          }
        auto operator*(void) const -> reference
          {
          return k_;
          }
        auto operator->(void) const -> pointer
          {
          return &k_;
          }
        auto operator++(void) -> const_iterator_base&
          {
          if(!end_)
            {
            end_=next_partition(k_,m_,end_);
            }
          return *this;
          }
        auto operator++(int) -> const_iterator_base
          {
          const_iterator_base ret = *this;
          ++(*this);
          return ret;
          }
        auto operator--(void) -> const_iterator_base&
          {
          if(end_)
            {
            end_=false;
            initialize_last(k_,m_,end_);
            }
          else
            {
            previous_partition(k_,m_,end_);
            }
          return *this;
          }
        auto operator--(int) -> const_iterator_base
          {
          const_iterator_base ret = (*this);
          --(*this);
          return ret;
          }
        auto operator==(const const_iterator_base& ci) const -> bool
          {
          return (end_==ci.end_) && (end_ || (k_==ci.k_ && m_==ci.m_));
          }
        auto operator!=(const const_iterator_base& ci) const -> bool
          {
          return !((*this)==ci);
          }
      };

    class all
      {
        int size_;
      public:

        all(int size)
          : size_(size)
          {
          assert(size>0);
          }
        auto size(void) const -> int
          {
          return size_;
          }

        using const_iterator = const_iterator_base<const_iterator_all>;

        auto begin(void) const -> const_iterator
          {
          return const_iterator(size(),false);
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator{size(),true};
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                   (const_iterator(size(),true));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                   (const_iterator(size(),false));
          }
      }; // class all
    ///////////////////////////////////////////////////////////////////
    class kblocks
      {
        int size_;
        int blocks_;
      public:

        kblocks(int dim, int blocks)
          : size_(dim),
            blocks_(blocks)
          {
          assert(dim>0);
          assert(blocks>0);
          assert(blocks<=dim);
          }
        auto size(void) const -> int
          {
          return size_;
          }
        auto blocks(void) const -> int
          {
          return blocks_;
          }

        using const_iterator = const_iterator_base<const_iterator_kblocks>;

        auto begin(void) const -> const_iterator
          {
          return const_iterator(size(),false,blocks());
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator{size(),true,blocks()};
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),true,blocks()));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),false,blocks()));
          }
      }; // class kblocks
    /////////////////////////////////////////////////////////////////
    } // namespace partitions_stateless
  } // namespace ljwo

There are a few things here that deserve a comment. They all stem from the fact that the blocks_ attribute is specific to one of the policies, but not to the other. It would be unreasonable to process it at the solution class (here called const_iterator_base), although the constructor of the solution class is the front–end to the whole compound. So any policy–specific argument has to be forwarded down to the policy’s constructor, but only when needed. How do we accomplish that? Policies in this solution have to define a typelist (here packaged as std::tuple) of arguments expected by their non–default constructor. This typelist is then appended to the constructor signature of the solution class. As I wrote in one of my previous posts, the only way to accomplish that is to make the constructor accept any argument pack and SFINAE–reject those that are inappropriate. I use here EnableIf as in the post Remastered enable_if by R. Martinho Fernadez. There is one thing that is still the cause for a slight bother: blocks_ must pass a sanity check, must not be greater than the size of the partitioned set, and the only place where we are able to assert on that is far outside the class where it is actually stored. Which gets us to the last design option.

2.2.3. Data in a common base class of the policy classes


Let me jump straight to the code:

namespace ljwo
  {
  namespace detail
    {
    enum class enabler {};
    }
      template <typename Condition>
  using EnableIf = typename std::enable_if
                              <
                              Condition::value, 
                              detail::enabler
                              >::type;

  namespace partitions_protected
    {
    typedef std::vector<int> partition;

    class const_iterator_impl
      {
      protected:
        bool end_;
        std::vector<int> k_;
        std::vector<int> m_;
        const_iterator_impl(void)
          : end_(true)
          {}
        const_iterator_impl(int dim, bool end=true)
          : end_(end),
            k_(dim),
            m_(dim)
          {
          assert(dim>0);
          }
      };

    class const_iterator_all : protected const_iterator_impl
      {
      protected:
        const_iterator_all(void){}
  //      using const_iterator_impl::const_iterator_impl; // also works instead

        using constructor_args = std::tuple<int,bool>;
        const_iterator_all(int dim, bool end=true)
          : const_iterator_impl(dim,end)
          {
          }
        auto initialize_first(void) -> void
          {
          std::fill(std::begin(k_),std::end(k_),0);
          std::fill(std::begin(m_),std::end(m_),0);
          }
        auto initialize_last(void) -> void
          {
          std::iota(std::begin(k_),std::end(k_),0);
          std::iota(std::begin(m_),std::end(m_),0);
          }
        auto next_partition(void) -> bool
          {
          int n = k_.size();
          bool not_found = true;
          for(int i=n-1; i>0; --i)
            if(k_[i]<=m_[i-1])
              {
              ++(k_[i]);
              m_[i]=std::max(m_[i],k_[i]);
              for(int j=i+1; j<n; ++j)
                {
                k_[j]=k_[0];
                m_[j]=m_[i];
                }
              not_found = false;
              break;
              }
          return not_found;
          }
        auto previous_partition(void) -> void
          {
          int n = k_.size();
          for(int i=n-1; i>0; --i)
            if(k_[i]>k_[0])
            // undefined behaviour if going before first
              {
              --(k_[i]);
              m_[i]=m_[i-1];
              for(int j=i+1; j<n; ++j)
                {
                m_[j]=m_[i]+j-i;
                k_[j]=m_[j];
                }
              break;
              }
          }
      }; // class const_iterator_all

    class const_iterator_kblocks : protected const_iterator_impl
      {
        int blocks_;
      protected:
        const_iterator_kblocks(void)
          : blocks_(0)
          {}
        using constructor_args = std::tuple<int,int,bool>;
        const_iterator_kblocks(int dim, int blocks, bool end=true)
          : const_iterator_impl(dim,end),
            blocks_(blocks)
          {
          assert(blocks>0);
          assert(blocks<=dim);
          }
        auto initialize_first(void) -> void
          {
          std::fill(std::begin(k_),std::end(k_)-blocks_,0);
          std::fill(std::begin(m_),std::end(m_)-blocks_,0);
          std::iota(std::end(k_)-blocks_,std::end(k_),0);
          std::iota(std::end(m_)-blocks_,std::end(m_),0);
          }
        auto initialize_last(void) -> void
          {
          std::iota(std::begin(k_),std::begin(k_)+blocks_,0);
          std::iota(std::begin(m_),std::begin(m_)+blocks_,0);
          int last = *(std::begin(k_)+blocks_-1);
          std::fill(std::begin(k_)+blocks_,std::end(k_),last);
          std::fill(std::begin(m_)+blocks_,std::end(m_),last);
          }
        auto next_partition(void) -> bool
          {
          int n = k_.size();
          bool not_found = true;
          for(int i=n-1; i>0; --i)
            if((k_[i]<blocks_-1) && (k_[i]<=m_[i-1]))
              {
              ++(k_[i]);
              m_[i]=std::max(m_[i],k_[i]);
              for(int j=i+1; j<=n-(blocks_-m_[i]); ++j)
                {
                k_[j]=0;
                m_[j]=m_[i];
                }
              for(int j=n-(blocks_-m_[i])+1; j<n; ++j)
                {
                m_[j]=blocks_-(n-j);
                k_[j]=m_[j];
                }
              not_found = false;
              break;
              }
          return not_found;
          }
        auto previous_partition(void) -> void
          {
          int n = k_.size();
          for(int i=n-1; i>0; --i)
            if((k_[i]>0) && (blocks_-m_[i-1]<=n-i))
            // undefined behaviour if going before first
              {
              --(k_[i]);
              m_[i]=m_[i-1];
              for(int j=i+1; j<=i+(blocks_-m_[i])-1; ++j)
                {
                m_[j]=m_[i]+j-i;
                k_[j]=m_[j];
                }
              for(int j=i+(blocks_-m_[i]); j<n; ++j)
                {
                m_[j]=blocks_-1;
                k_[j]=m_[j];
                }
              break;
              }
          }
      }; // class const_iterator_kblocks

        template<class const_iterator_spec>
    class const_iterator_base : public std::iterator
                                         <
                                         std::bidirectional_iterator_tag,
                                         const partition
                                         >,
                                protected const_iterator_spec
      {
      public:
 //       using const_iterator_spec::const_iterator_spec;
 //       the above is impossible since base constructors are protected
        using const_iterator_spec::initialize_first;
        using const_iterator_spec::initialize_last;
        using const_iterator_spec::next_partition;
        using const_iterator_spec::previous_partition;
        using const_iterator_spec::end_;
        using const_iterator_spec::k_;
        using const_iterator_spec::m_;

        const_iterator_base(void)
          {}

            template<class... Args,
                     EnableIf
                       <
                       std::is_same
                         <
                         std::tuple<Args...>,
                         typename const_iterator_spec::constructor_args
                         >
                       >...
                    >
        const_iterator_base(Args... args)
          : const_iterator_spec(std::forward<Args>(args)...)
          {
          initialize_first();
          }
        auto operator*(void) const -> reference
          {
          return k_;
          }
        auto operator->(void) const -> pointer
          {
          return &k_;
          }
        auto operator++(void) -> const_iterator_base&
          {
          if(!end_)
            {
            end_=next_partition();
            }
          return *this;
          }
        auto operator++(int) -> const_iterator_base
          {
          const_iterator_base ret = *this;
          ++(*this);
          return ret;
          }
        auto operator--(void) -> const_iterator_base&
          {
          if(end_)
            {
            end_=false;
            initialize_last();
            }
          else
            {
            previous_partition();
            }
          return *this;
          }
        auto operator--(int) -> const_iterator_base
          {
          const_iterator_base ret = (*this);
          --(*this);
          return ret;
          }
        auto operator==(const const_iterator_base& ci) const -> bool
          {
          return (end_==ci.end_) && (end_ || (k_==ci.k_ && m_==ci.m_));
          }
        auto operator!=(const const_iterator_base& ci) const -> bool
          {
          return !((*this)==ci);
          }
      };

    class all
      {
        int size_;
      public:
        all(int size)
          : size_(size)
          {
          assert(size>0);
          }
        auto size(void) const -> int
          {
          return size_;
          }

        using const_iterator = const_iterator_base<const_iterator_all>;

        auto begin(void) const -> const_iterator
          {
          return const_iterator(size(),false);
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator{size(),true};
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                   (const_iterator(size(),true));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                   (const_iterator(size(),false));
          }
      }; // class all
    //////////////////////////////////////////////////////////////////
    class kblocks
      {
        int size_;
        int blocks_;
      public:
        kblocks(int dim, int blocks)
          : size_(dim),
            blocks_(blocks)
          {
          assert(dim>0);
          assert(blocks>0);
          assert(blocks<=dim);
          }
        auto size(void) const -> int
          {
          return size_;
          }
        auto blocks(void) const -> int
          {
          return blocks_;
          }

        using const_iterator = const_iterator_base<const_iterator_kblocks>;

        auto begin(void) const -> const_iterator
          {
          return const_iterator(size(),blocks(),false);
          }
        auto end(void) const -> const_iterator
          {
          return const_iterator{size(),blocks(),true};
          }
        auto rbegin(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),blocks(),true));
          }
        auto rend(void) const -> std::reverse_iterator<const_iterator>
          {
          return std::reverse_iterator<const_iterator>
                        (const_iterator(size(),blocks(),false));
          }
      }; // class kblocks
    //////////////////////////////////////////////////////////////////
    } // namespace partitions_protected
  } // namespace ljwo

In this solution, common data is defined in the class const_iterator_impl that is base to all the policies. Since this data is used by its offspring, it is made protected, but to make it visible, inheritance also has to be protected. Other quirks are similar to those of the previous design, the solution constructor now forwards everything down according to the typelist and data sanity is asserted in classes where it is stored.

To me, this solution just Feels Right™. Also, I must admit it is the first time in my 22-years experience with c++ that I find a natural use for protected inheritance. I wonder what is your mileage.

3. There’s always the unexpected


I promised that I would be asessing speed of the solutions. I expected the manual and the two complete policy–based solutions for all partitions to run in similar time, and I already mentioned that the virtual–function based solution typically runs 40-50% slower. But, trying to figure out the behaviour of the different solutions I found results quite unexpected for me. The two factors that seem to matter most are first the presence of the restricted partitions code in the compilation, and second, the use of the atribute flatten on the test functions. I structured the tests accordingly, test2 does only all partitions, test3 only restricted partitions, and test4 does all. Each has three possible statuses, absent (0), present (1) and present with flatten (2). The code for the tests is given below, the bash script to build and run them further below, and the results table after that.

auto
#if TEST2==2
  __attribute__((flatten))
#endif
test2(std::string db, std::string de, std::ostream& out) -> void
  {
#if TEST2>0
  double s[4]{};
  const int repeat = 50;
  for(int i=0; i<10; ++i)
    {
    s[0] += test_partitions<ljwo::partitions_straight::all>(repeat);
    s[1] += test_partitions<ljwo::partitions_virtual::all>(repeat);
    s[2] += test_partitions<ljwo::partitions_stateless::all>(repeat);
    s[3] += test_partitions<ljwo::partitions_protected::all>(repeat);
    }
  for(int i=0; i<4; ++i)
    out << db << std::setw(3) << std::round(s[i]/1e8) << de;
#else
  for(int i=0; i<4; ++i)
    out << db << "   " << de;
#endif
  }

auto
#if TEST3==2
__attribute__((flatten))
#endif
test3(std::string db, std::string de, std::ostream& out) -> void
  {
#if TEST3>0
  double s[3]{};
  const int repeat = 50;
  for(int i=0; i<10; ++i)
    {
    s[0] += test_kblocks_partitions<ljwo::partitions_virtual::kblocks>(repeat);
    s[1] += test_kblocks_partitions<ljwo::partitions_stateless::kblocks>(repeat);
    s[2] += test_kblocks_partitions<ljwo::partitions_protected::kblocks>(repeat);
    }
  for(int i=0; i<3; ++i)
    out << db << std::setw(3) << std::round(s[i]/1e8) << de;
#else
  for(int i=0; i<3; ++i)
    out << db << "   " << de;
#endif
  }

auto
#if TEST4==2
__attribute__((flatten))
#endif
test4(std::string db, std::string de, std::ostream& out) -> void
  {
#if TEST4>0
  double s[7]{};
  const int repeat = 50;
  for(int i=0; i<10; ++i)
    {
    s[0] += test_partitions<ljwo::partitions_straight::all>(repeat);
    s[1] += test_partitions<ljwo::partitions_virtual::all>(repeat);
    s[2] += test_partitions<ljwo::partitions_stateless::all>(repeat);
    s[3] += test_partitions<ljwo::partitions_protected::all>(repeat);
    s[4] += test_kblocks_partitions<ljwo::partitions_virtual::kblocks>(repeat);
    s[5] += test_kblocks_partitions<ljwo::partitions_stateless::kblocks>(repeat);
    s[6] += test_kblocks_partitions<ljwo::partitions_protected::kblocks>(repeat);
    }
  for(int i=0; i<7; ++i)
    out << db << std::setw(3) << std::round(s[i]/1e8) << de;
#else
  for(int i=0; i<7; ++i)
    out << db << "   " << de;
#endif
  }

auto main(void) -> int
  {
  test2(" "," ",std::cout);
  std::cout << std::flush;
  test3(" "," ",std::cout);
  std::cout << std::flush;
  test4(" "," ",std::cout);
  std::cout << std::flush;
  }

And the build and run script, that starts with a warmup phase to get all the throttles of the machine into stationary state:

#!/bin/bash
echo "<pre>" > r.txt
echo -n "T2  T3  T4 | " >> r.txt
echo -n "t2as t2av t2al t2ap " >> r.txt
echo -n "t3kv t3kl t3kp " >> r.txt
echo -n "t4as t4av t4al t4ap " >> r.txt
echo    "t4kv t4kl t4kp " >> r.txt
for v in `seq 0 3`;
  do
  echo "warmup " $v
  g++ -std=c++11 -O3 -DTEST2=1 -DTEST3=1 -DTEST4=1 -march=native \
      -c main.cpp -o obj/Release/main.o
  g++ -o bin/Release/part obj/Release/main.o -s
  bin/Release/part > /dev/null
  done
for s in `seq 0 2`;
  do
  for t in `seq 0 2`;
    do
    for u in `seq 0 2`;
      do
      echo "test case " $s $t $u
      g++ -std=c++11 -O3 -DTEST2=$s -DTEST3=$t -DTEST4=$u -march=native \
          -c main.cpp -o obj/Release/main.o
      g++ -o bin/Release/part obj/Release/main.o -s
      echo -n " "$s"   "$t"   "$u" | " >> r.txt
      bin/Release/part >> r.txt
      echo "" >> r.txt
      done
    done
  done
echo "</pre>" >> r.txt

This ran on my dell latitude E6420 with a 2.5GHz Core i5-2520M CPU, 4GB RAM and Debian Jessie 64-bit with gcc 4.9.2 for about an hour and a quarter, of which the quarter was warmup, and produced the following table, where the first part of the headings encodes the test functions, t2, t3, t4, then the type of partitions a for all, k for kblocks, and finally the design, s for straight, v for virtual, l for stateless, p for protected:

T2  T3  T4 | t2as t2av t2al t2ap t3kv t3kl t3kp t4as t4av t4al t4ap t4kv t4kl t4kp 
 0   0   0 |                                                                       
 0   0   1 |                                      97  147   98  113  203  206  206 
 0   0   2 |                                     102   94   95   97  214  216  213 
 0   1   0 |                      189  205  207                                    
 0   1   1 |                      195  201  213   93  146   94  113  194  201  214 
 0   1   2 |                      195  203  205  100   93   95   97  215  218  215 
 0   2   0 |                      203  206  202                                    
 0   2   1 |                      207  204  203   94  145   95  128  196  204  206 
 0   2   2 |                      204  205  201  104   94   97   98  217  219  221 
 1   0   0 |   97  146   91   94                                                   
 1   0   1 |  100  149  102  120                 100  149  102  120  202  215  193 
 1   0   2 |   98  150   94   95                 107   98   97  101  225  224  229 
 1   1   0 |   93  144   91  110  203  215  207                                    
 1   1   1 |  100  147  102  119  206  209  217  100  147  101  119  201  203  211 
 1   1   2 |   93  145   91  111  203  207  206  101   94   96   97  216  218  217 
 1   2   0 |   94  144   92   92  202  212  211                                    
 1   2   1 |   94  148   99  120  202  204  201   93  147   99  119  203  206  194 
 1   2   2 |   96  145   91   91  203  205  202  102   94   95   97  220  219  221 
 2   0   0 |  101   96   95   95                                                   
 2   0   1 |  102   99   94   98                  92  145   91  114  209  205  203 
 2   0   2 |  100   96   94   95                 103   93   95   96  217  220  222 
 2   1   0 |  102   99   94   97  202  206  211                                    
 2   1   1 |  105  100   97  103  202  202  214   92  145   93  110  201  205  246 
 2   1   2 |  104  100   97  105  202  203  206  101   94   95   97  214  216  213 
 2   2   0 |  100   96   95   95  206  203  203                                    
 2   2   1 |  102   99   95   98  203  205  202   92  146   91  114  208  206  205 
 2   2   2 |  105   97   97  104  207  204  203  174  101   97  100  367  375  374 

There are a few things that stand out in this table. Test2 (only all partitions) built without flatten (1yz) shows that the virtual solution is the slowest, while the straight and stateless are faster and on par. A strange things happens to the protected solution: it is on par with staright and stateless, but only if no other not-flatten test function involving restricted partitions is built (you don’t even have to run it), otherwise it gets some 20% performance hit. Corresponding to that are all-partitions protected figures in non-flatten test4 that are worse than straight and stateless but beter than virtual.

Test2 built with flatten is most strange. The straight solution gets a 10% hit (how come?), while the others, including the virtual one, are roughly on par (some figures are higher, but I see no regularity so I assume it’s noise). Virtual better than straight?? Some very clever devirtualizer of gcc must have kicked in. The same pattern can be observed in all-partitions results of test4 with flatten.

Test3, involving restricted partitions, runs fastest for the virtual design but without flatten (unlike test2), regardless of whether test4 is built, but only if test2 is not built. Frankly, I don’t understand, but that’s the pattern. It can also be seen in restricted partitions’ results in test4 (except the 203 figure for t4kv at 001, but maybe that’s noise again? the difference is not large). Also, the results for the stateless and protected designs show a degradation for some test cases, but without an apparent regularity.

And finally, test4’s last line (222, all tests built with flatten) shows some serious outliers with no obvious explanation.

I also ran the same test suite using g++ 4.8.4. The resulting code took more time, it ran for 1:35 on the same machine, and the detailed figures show it, albeit with fewer surprises:

T2  T3  T4 | t2as t2av t2al t2ap t3kv t3kl t3kp t4as t4av t4al t4ap t4kv t4kl t4kp 
 0   0   0 |                                                                       
 0   0   1 |                                     133  228  111  120  346  231  197 
 0   0   2 |                                     111  198  110  105  296  233  232 
 0   1   0 |                      334  227  222                                    
 0   1   1 |                      323  220  202  110  230  105  118  323  220  202 
 0   1   2 |                      335  228  223  114  196  111  106  298  233  234 
 0   2   0 |                      288  232  238                                    
 0   2   1 |                      300  223  227  134  221  112  119  334  231  200 
 0   2   2 |                      286  231  237  104  195  102  101  287  227  228 
 1   0   0 |  103  212  106  112                                                   
 1   0   1 |  107  213  111  118                 107  213  111  118  322  224  190 
 1   0   2 |  104  221  107  113                 111  197  109  104  297  234  233 
 1   1   0 |  103  212  112  118  310  223  195                                    
 1   1   1 |  108  213  111  121  311  229  195  108  213  111  121  311  229  195 
 1   1   2 |  104  221  110  118  321  221  194  112  196  111  105  299  234  235 
 1   2   0 |  114  221  116  113  299  258  273                                    
 1   2   1 |  109  222  115  118  296  223  227  109  223  115  118  318  235  210 
 1   2   2 |  116  212  118  114  307  231  237  111  197  103  103  286  231  362 
 2   0   0 |  108  197  101  112                                                   
 2   0   1 |  106  197  109  122                 133  222  111  119  331  231  197 
 2   0   2 |  112  195  101  116                 103  196  105  100  286  227  228 
 2   1   0 |  105  197  109  122  323  222  221                                    
 2   1   1 |  106  195  101  113  311  227  202  112  211  103  117  311  227  202 
 2   1   2 |  105  195  109  114  309  224  222  103  211  102  102  310  227  226 
 2   2   0 |  112  209  101  116  288  224  228                                    
 2   2   1 |  105  195  109  114  289  232  237  119  220  103  111  311  244  206 
 2   2   2 |  113  197  101  116  299  224  228  111  197  110  105  299  234  235 

As before, turning flatten on optimizes the virtual design in the all-partitions case, but not nearly as much as with 4.9.2, with the protected design being slightly worse than stateless and straight but only in test2 and not in test4. The best results for the restricted partitions are seen with the protected design, in test3 for cases 11z and in test4 for all non-flatten builds. The value 362 for t4kp at 122 is probably an artifact, no such outlier was present in the experiment I ran on another machine.

4. Conclusion


The timing results are confusing. Sometimes the protected design performed well, sometimes it was slower than others. I guess that it might be that gcc’s optimizer is not used to this exotic pattern. So my choice would be protected as I like the design, but if you need every millisecond, you may consider the other ones, but you need to measure your particular application together with your compiler and hardware. I was wondering what the difference is on the level of machine code corresponding to the various cases, but I did not have the stamina to go into it, and this post already got grotesquely oversized, the web-editor for the blog is choking, and it may well crash on me if I do not stop. Let me just thank you for your reading, and if you made it this far, would you care to let me know about it in a comment?

Advertisements

6 Responses to Generating set partitions – replacing virtual functions with protected inheritance

  1. Eric says:

    There seems to be a bug in Michael’s algorithm for p-partitions (unless I’ve implemented something wrong, I’m not using the C++ implementations but did mine with haskell and scala). When I generate all the 3 partitions of [1..5] I don’t get [[1,2,5],[3],[4]]. Do you have the same issue as well?

    • ljwo says:

      Hi Eric, thanks for reading. Just ran all the three implementations with (5,3) parameters, and all of them produced 0,0,1,2,0 among the results, which corresponds to [[1,2,5],[3],[4]]. Would you like to share your functional implementations? I know the code I posted shows what some consider to be the worst aspects of c++ (I like it this way, though), but in this case it had the advantage of easy implementation of imperative algorithms.

      • Eric says:

        Thanks for checking that for me. I missed the “break” in your implementation so I was skipping some elements. Now my Scala non-functional implementation is working fine and I’m still finalizing the Haskell one.

        The only overall issue with that algorithm is that I want the sets to be enumerated in an order which corresponds to the p-partitions of an integer n. For example, for p = 3 and n = 5, I want all the partitions having sets of sizes (3,1,1) coming before the ones having sizes (2,2,1).

        My overall goal is to find a fast algorithm to go from the index of a partition in the enumeration of all the partitions to the partition itself (without having to build all the partitions until I reach the desired one).

        Anyway, thanks for your help.

        • ljwo says:

          I don’t like the ‘break’, it’s hard to read, and I try to avoid it, but here it allowed for an exact step-by-step implementation of Michael’s pseudo-code. I see what you need, but I have no ready hints for you. I would start looking for elements of a solution in the monograph `Combinatorics of Set Partitions’ by Toufik Mansour, but you certainly know it.

          • Eric says:

            No I didn’t know it (I’m very new to that combinatorics field) and I thank you. I’m going to have a look at this book and send an email to the author to see if he can tilt me in the right direction.

            • ljwo says:

              Glad I could be of help. Let me know, please, if you come up with a solution, I would be very interested to get to know that.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: