Permutation.cpp

Go to the documentation of this file.

#include <iostream>
#include <limits>
#include <stdexcept>
#include <assert.h>

#include "Permutation.h"

using namespace doci;

Permutation::Permutation(unsigned int n)
{
   if(sizeof(mybitset)*8 < n)
      throw std::overflow_error("Cannot store permutations in assigned type");

   this->n = n;

   // set n lowest bits to 1
   reset();
}

mybitset Permutation::next()
{
#if defined(USELONG)
#define MY_CTZ(x) __builtin_ctzl(x)
#elif defined(USELONGLONG)
#define MY_CTZ(x) __builtin_ctzll(x)
#endif
 
   // current permutation of bits 
   auto &v = current; // current permutation of bits 

   // from https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
   auto t = v | (v - 1); // t gets v's least significant 0 bits set to 1
   // Next set to 1 the most significant bit to change, 
   // set to 0 the least significant ones, and add the necessary 1 bits.
   auto w = (t + 1) | (((~t & -~t) - 1) >> (MY_CTZ(v) + 1));

   // new/next permutation of bits
   current = w;

   return current;
}

mybitset Permutation::get() const
{
   return current;
}

void Permutation::reset()
{
   current = (1L<<n)-1L;
}

unsigned long long Permutation::CalcCombinations(unsigned int L, unsigned int N)
{
   assert(L >= N);

   if(0 == L)
      return 0;
   if(0 == N)
      return 1;
   if(L == N)
      return 1;
   if(1 == N)
      return L;

   unsigned long long result = 1;

   for(unsigned int i=1;i<=N;++i, --L)
   {
      auto g = gcd(result, i);
      result /= g;
      auto t = L / (i / g);

      if(result > std::numeric_limits<unsigned long long>::max() / t)
         throw std::overflow_error("Overflow in CalcCombinations");

      result *= t;
   }

   return result;
}

unsigned long long Permutation::gcd(unsigned long long x, unsigned long long y)
{
   assert(x >= y);

    while (y != 0)
    {
        unsigned long long t = x % y;
        x = y;
        y = t;
    }

    return x;
}

unsigned int Permutation::getMax()
{
   return sizeof(mybitset)*8;
}

/* vim: set ts=3 sw=3 expandtab :*/