295_intermediate.cpp

#include <iostream>
#include <vector>
#include <array>
#include <unordered_set>
#include <algorithm>
#include <functional>

using std::cout;
using std::unordered_set;

// we need to represent the circular table
template<int N>
struct circular_table {
    
    // initialize the table with N couples
    circular_table() {
        for( int i = 0; i < N; ++i ) {
            ap[i*2] = (i+1);
            ap[i*2+1] = -(i+1);
        }
        std::sort(ap.begin(), ap.end());
    }
    
    bool is_valid() const {
        if ( std::abs(first()) == std::abs(last()) ) return false;
        for( int i = 0; i < N*2-1; ++i ) {
            if ( std::abs(ap[i]) == std::abs(ap[i+1]) ) return false;
        }
        return true;
    }
    
    int first() const { return ap[0]; }
    int last () const { return ap[N*2-1]; }
    
    void print() {
        for( auto && i: ap ) cout << i << " ";
        cout << "\n";
    }
    
    bool operator==(circular_table<N> const & o) const {
        auto b = std::find(o.ap.begin(), o.ap.end(), ap[0]);
        container_type ap2;
        auto o2 = std::rotate_copy(o.ap.begin(), b, o.ap.end(), ap2.begin());
        return ap == ap2;
    }

    typedef std::array<int, N*2> container_type;
    container_type ap;
};


namespace std {
    template<int N>
    struct hash<circular_table<N>> {
        auto operator()(circular_table<N> const & ct) const -> std::size_t {
            // return the same number to force operator== usage.
            return 0;
        }
    };
}

template<int N>
int count_valid_permutations() {
    int i = 0;
    circular_table<N> t;
    unordered_set<circular_table<N>> tset;
    while ( std::next_permutation(t.ap.begin(), t.ap.end()) ) {
        if ( t.is_valid() )
            tset.insert(t);
    }
    
    return tset.size();
}

int main(int argc, char* argv[]) {
    cout << "n=1: " << count_valid_permutations<1>() << '\n';
    cout << "n=2: " << count_valid_permutations<2>() << '\n';
    cout << "n=3: " << count_valid_permutations<3>() << '\n';
    cout << "n=4: " << count_valid_permutations<4>() << '\n';
}