Skip to content

Instantly share code, notes, and snippets.

@OpenNingia
Created December 20, 2016 17:01
Show Gist options
  • Save OpenNingia/b0e6551ca452d586faf9ad13d1f61789 to your computer and use it in GitHub Desktop.
Save OpenNingia/b0e6551ca452d586faf9ad13d1f61789 to your computer and use it in GitHub Desktop.
#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';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment