OKlibrary  0.2.1.6
Combinatorics.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 21.4.2003 (Swansea)
00002 /* Copyright 2003 - 2007, 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00014 #ifndef COMBINATORICSWAECHTER
00015 
00016 #define COMBINATORICSWAECHTER
00017 
00018 #include <algorithm>
00019 #include <functional>
00020 #include <vector>
00021 #include <numeric>
00022 #include <cassert>
00023 #include <iostream>
00024 #include <iterator>
00025 
00026 #include <OKlib/General/ErrorHandling.hpp>
00027 #include <OKlib/General/FunctionHandling.hpp>
00028 
00029 namespace Combinatorics {
00030 
00031   struct Error : ErrorHandling::Error {
00032     Error(const std::string& what) : ErrorHandling::Error(what) {}
00033   };
00034 
00035 }
00036 
00037 namespace Combinatorics {
00038   
00039   // -------------------------------------------------------------
00040   // Elementary counting
00041   // -------------------------------------------------------------
00042 
00048   template <typename Int>
00049   struct Factorial {
00050     Int operator() (const Int n) const {
00051       const Int zero(0);
00052       assert(n >= zero);
00053       Int f(1);
00054       for (unsigned int i = Int(2); i <= n; ++i)
00055         f *= i;
00056       return f;
00057     }
00058   };
00059   template <typename Int>
00060   inline Int factorial(const Int& n) {
00061     return Factorial<Int>()(n);
00062   }
00063 
00069   template <typename Num, typename Int>
00070   struct Descending_power {
00071     Num operator() (Num b, Int k) const {
00072       const Int zero(0);
00073       assert(k >= zero);
00074       Num p(1);
00075       for (Int i = zero; i != k; --b, ++i)
00076   p *= b;
00077       return p;
00078     }
00079   };
00080   template <typename Num, typename Int>
00081   inline Num descending_power(Num b, Int k) {
00082     return Descending_power<Num, Int>()(b, k);
00083   }
00084 
00093   template <typename Int>
00094   struct Binom_integer_over_integer {
00095     Int operator() (Int n, Int k) const {
00096       
00097       if (k < Int(0)) return Int(0);
00098       if (k == Int(0)) return Int(1);
00099       assert(k > Int(0));
00100       if (k == Int(1)) return n;
00101       assert(k >= Int(2));
00102       if (n == Int(0)) return Int(0);
00103       if (n == k) return Int(1);
00104       if (n == Int(-1)) return Int(1);
00105       if (n < 0)
00106         n = k - n - Int(1);
00107       else
00108         if (n < k) return Int(0);
00109       assert(n > Int(0));
00110       assert(k < n);
00111       if (n < Int(2) * k)
00112         k = n - k;
00113       assert(Int(2) * k <= n);
00114       assert(k > Int(0));
00115       if (k == Int(1)) return n;
00116       assert(k >= Int(2));
00117       // XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
00118 
00119       typedef typename std::vector<Int> vector_type;
00120       typedef typename vector_type::iterator iterator;
00121       vector_type v;
00122       v.reserve(k+1);
00123       v.push_back(1); v.push_back(1);
00124       iterator first = v.begin();
00125       const Int diff = n - k;
00126       for (Int i = Int(2); i <= n; ++i) {
00127         std::adjacent_difference(first, v.end(), first, std::plus<Int>());
00128         if (i <= k) v.push_back(1);
00129         if (i > diff) ++first;
00130       }
00131       return *first;
00132     }
00133   };
00134   template <typename Int>
00135   inline Int binom_integer_over_integer(const Int z, const Int k) {
00136     return Binom_integer_over_integer<Int>()(z, k);
00137   }
00138   template <typename Int>
00139   inline Int binom(Int a, Int b) {
00140     return Binom_integer_over_integer<Int>()(a, b);
00141   }
00142 
00143   
00144   // -------------------------------------------------------------
00145   // Elementary enumeration
00146   // -------------------------------------------------------------
00147 
00168   enum choose_possibilities {no_subsets = -1, no_further_subsets = 0, further_subsets = 1};
00169   template <typename Int, class ForwardIterator>
00170   choose_possibilities choose_next(const Int n, const Int k, const ForwardIterator begin, const ForwardIterator end) {
00171     // Assigns to the range [begin, end) the next k-subset of {0,1, ..., n-1}
00172     const Int zero(0);
00173 
00174     if (n < zero or k > n or k < zero) return no_subsets;
00175     if (k == zero or k == n) return no_further_subsets;
00176 
00177     assert(std::distance(begin, end) == k);
00178     assert(std::adjacent_find(begin, end, std::greater_equal<Int>()) == end);
00179     assert(std::find_if(begin, end, std::not1(FunctionHandling::in_right_open_interval<Int>(zero, Int(n)))) == end);
00180 
00181     Int v = *begin; ++v;
00182     ForwardIterator first_candidate = begin;
00183     {
00184       ForwardIterator next = begin;
00185       for (; ++next != end and *next == v; first_candidate = next, ++v);
00186     }
00187     if (v == n) return no_further_subsets;
00188     assert(v < n and *first_candidate == v - 1);
00189     *first_candidate = v;
00190     std::generate(begin, first_candidate, FunctionHandling::Counter<Int>());
00191     return further_subsets;
00192   }
00193 }
00194 
00195 #endif