combinations.h

Go to the documentation of this file.

#ifndef TPCC_COMBINATIONS_H
#define TPCC_COMBINATIONS_H
 
#include <array>
#include <cassert>
#include <ostream>
 
namespace TPCC
{
template <typename T = unsigned int>
constexpr T binomial(T n, T k)
{
  if (n < k)
    return 0;
  T result = 1;
  if (k > n / 2)
    k = n - k;
  for (T i = 1; i <= k; ++i)
  {
    result *= n + 1 - i;
    result /= i;
  }
 
  return result;
}
 
template <typename T = unsigned int, T n, T k>
constexpr std::array<T, n - k> compute_complement(std::array<T, k> combi)
{
  std::array<unsigned int, n - k> result{};
  unsigned int vpos = 0;
  unsigned int current = n - 1;
 
  for (unsigned int i = 0; i < n - k; ++i, --current)
  {
    while (vpos < k && current == combi[vpos])
    {
      --current;
      ++vpos;
    }
    result[i] = current;
  }
  return result;
}
 
template <int n, int k, typename T = unsigned int>
class Combination
{
  std::array<T, k> data;
  std::array<T, n - k> cdata;
 
public:
  Combination(const std::array<T, k>& combi, const std::array<T, n - k>& comp)
    : data(combi)
    , cdata(comp)
  {
  }
  T in(unsigned int i) const { return data[i]; }
  T out(unsigned int i) const { return cdata[i]; }
 
  Combination<n, n - k, T> complement() const { return Combination<n, n - k, T>(cdata, data); }
 
  template <int kk = k>
  constexpr typename std::enable_if<(kk > 0), Combination<n, k - 1, T>>::type eliminate(
    unsigned int i) const
  {
    std::array<T, k - 1> outdata{};
    for (unsigned int j = 0; j < i; ++j)
      outdata[j] = data[j];
    const T tmp = data[i];
    for (unsigned int j = i; j < k - 1; ++j)
      outdata[j] = data[j + 1];
 
    std::array<T, n - k + 1> outcdata{};
    unsigned int jj = 0, j = 0;
    for (; j < n - k; ++j, ++jj)
    {
      if (jj == j && cdata[j] < tmp)
      {
        outcdata[j] = tmp;
        ++jj;
      }
      outcdata[jj] = cdata[j];
    }
    if (jj == j)
      outcdata[n - k] = tmp;
    return Combination<n, k - 1>{ outdata, outcdata };
  }
  template <int kk = k>
  constexpr typename std::enable_if<(kk < n), Combination<n, k + 1, T>>::type add(
    unsigned int i) const
  {
    std::array<T, k + 1> outdata{};
    int jj = 0, j = 0;
    for (; j < k; ++j, ++jj)
    {
      if (jj == j && data[j] <= i)
      {
        assert(data[j] != i);
        outdata[j] = i;
        ++jj;
      }
      outdata[jj] = data[j];
    }
    if (jj == j)
      outdata[k] = i;
 
    std::array<T, n - k - 1> outcdata{};
    j = 0;
    jj = 0;
    for (; j < n - k - 1; ++j, ++jj)
    {
      if (cdata[j] == i)
        ++jj;
      outcdata[j] = cdata[jj];
    }
    return Combination<n, k + 1>{ outdata, outcdata };
  }
 
  template <int kk = k>
  constexpr typename std::enable_if<(kk <= n), Combination<n + 1, k + 1, T>>::type add_and_expand(
    unsigned int i) const
  {
    std::array<T, n + 1 - k> outcdata{};
    std::copy(cdata.begin(), cdata.end(), outcdata.begin());
    outcdata[n - k] = n;
    return Combination<n + 1, k>{ data, outcdata }.add(i);
  }
 
  void print_debug(std::ostream& os) const
  {
    for (int i = 0; i < k; ++i)
      os << in(i);
    os << ':';
    for (int i = 0; i < n - k; ++i)
      os << out(i);
  }
};
 
template <int n, int k>
struct Combinations
{
  static constexpr unsigned int size();
 
  constexpr Combination<n, k> operator[](unsigned int);
 
  static std::array<unsigned int, k> value(unsigned int index);
  static std::array<unsigned int, n - k> dual(unsigned int index);
 
  template <typename T>
  static constexpr unsigned int index(const Combination<n, k, T>& combi);
 
private:
  template <unsigned int size, typename... I>
  static constexpr std::array<unsigned int, k> compute_value(unsigned int index, I... args);
};
 
//----------------------------------------------------------------------//
 
template <int n, int k>
constexpr unsigned int Combinations<n, k>::size()
{
  return binomial(n, k);
}
 
template <int n, int k>
template <unsigned int sz, typename... I>
constexpr std::array<unsigned int, k> Combinations<n, k>::compute_value(unsigned int index,
                                                                        I... args)
{
  if (index > size())
    abort();
  if constexpr (sz == 1)
    return std::array<unsigned int, k>{ args..., index };
  else
  {
    unsigned int cs = sz - 1;
    unsigned int bn = 0;
    for (; cs <= n; ++cs)
    {
      unsigned int bi = binomial(cs, sz);
      if (bi > index)
        break;
      bn = bi;
    }
    --cs;
    return compute_value<sz - 1>(index - bn, args..., cs);
  }
}
 
template <int n, int k>
template <typename T>
inline constexpr unsigned int Combinations<n, k>::index(const Combination<n, k, T>& combi)
{
  unsigned int result = 0;
  if constexpr (k > 0)
    for (unsigned int i = 0; i < k; ++i)
      result += binomial(combi.in(i), k - i);
  return result;
}
 
//----------------------------------------------------------------------//
 
template <int n, int k>
std::array<unsigned int, k> Combinations<n, k>::value(unsigned int index)
{
  if constexpr (k == 0)
  {
    ++index; // Avoid warning about unused variable
    return std::array<unsigned int, 0>();
  }
  else
    return compute_value<k>(index);
}
 
template <int n, int k>
std::array<unsigned int, n - k> Combinations<n, k>::dual(unsigned int index)
{
  if constexpr (k == 0)
    return Combinations<n, n>::value(index);
  auto v = value(index);
  return compute_complement<unsigned int, n, k>(v);
}
 
template <int n, int k>
constexpr Combination<n, k> Combinations<n, k>::operator[](unsigned int index)
{
  return Combination<n, k>(value(index), dual(index));
}
} // namespace TPCC
 
#endif