Combinatorics.hpp

Go to the documentation of this file.

#ifndef AI_TOOLBOX_UTILS_COMBINATORICS_HEADER_FILE
#define AI_TOOLBOX_UTILS_COMBINATORICS_HEADER_FILE
 
#include <vector>
#include <numeric>
#include <cassert>
 
namespace AIToolbox {
    unsigned nChooseK(unsigned n, unsigned k);
 
    unsigned starsBars(unsigned stars, unsigned bars);
 
    unsigned ballsBins(unsigned balls, unsigned bins);
 
    unsigned nonZeroStarsBars(unsigned stars, unsigned bars);
 
    unsigned nonZeroBallsBins(unsigned balls, unsigned bins);
 
    template <typename Index>
    class SubsetEnumerator {
        public:
            using IdsStorage = std::vector<Index>;
 
            SubsetEnumerator(size_t elementsN, Index lowerBound, Index upperBound) :
                    lowerBound_(lowerBound), upperBound_(upperBound), ids_(elementsN)
            {
                if constexpr (std::is_integral_v<Index>) {
                    assert(upperBound_ > lowerBound_);
                    assert(static_cast<size_t>(upperBound_ - lowerBound_) >= elementsN);
                } else
                    assert(static_cast<size_t>(std::distance(lowerBound_, upperBound_)) >= elementsN);
                reset();
            }
 
            auto advance() {
                auto current = ids_.size() - 1;
                auto ub = upperBound_ - 1;
                while (current && ids_[current] == ub) --current, --ub;
 
                auto lowest = current; // Last element we need to change.
                ub = ++ids_[current];
 
                while (++current != ids_.size()) ids_[current] = ++ub;
 
                return lowest;
            }
 
            bool isValid() const {
                return ids_.back() < upperBound_;
            }
 
            void reset() {
                std::iota(std::begin(ids_), std::end(ids_), lowerBound_);
            }
 
            auto subsetsSize() const {
                if constexpr (std::is_integral_v<Index>)
                    return nChooseK(upperBound_ - lowerBound_, ids_.size());
                else
                    return nChooseK(std::distance(lowerBound_, upperBound_), ids_.size());
            }
 
            auto size() const { return ids_.size(); }
 
 
            const IdsStorage& operator*() const {
                return ids_;
            }
 
            const IdsStorage* operator->() const {
                return &ids_;
            }
 
        private:
            Index lowerBound_, upperBound_;
            IdsStorage ids_;
    };
}
 
#endif