fork download
copy 
  1. #include <random>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5. #include <iostream>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. template <int n>
  11. struct permutation {
  12.     // prefer 1-based indices
  13.     permutation() { for (int i = 0; i <= n; ++i) v_.push_back(i); }
  14.  
  15.     static constexpr int size() { return n; }
  16.  
  17.     static permutation  id() { return permutation(); }
  18.     static permutation  loop(const vector<int> idx) {
  19.         permutation res;
  20.         for (int i = 0; i + 1 < idx.size(); ++i)
  21.             res.v_[idx[i]] = idx[i + 1];
  22.         res.v_[*idx.rbegin()] = idx[0];
  23.         return res;
  24.     }
  25.  
  26.     const vector<int>&  data() const { return v_; }
  27.     int                 operator[](int i) const { return v_[i]; }
  28.     bool                operator==(const permutation& r) const { return v_ == r.v_; }
  29.     bool                operator<(const permutation& r) const { return v_ < r.v_; }
  30.  
  31.     permutation         operator*(const permutation& r) const {
  32.         permutation res;
  33.         for (int i = 1; i <= n; ++i)
  34.             res.v_[i] = (*this)[r[i]];
  35.         return res;
  36.     }
  37.     permutation         inv() const {
  38.         permutation res;
  39.         for (int i = 1; i <= n; ++i)
  40.             res.v_[v_[i]] = i;
  41.         return res;
  42.     }
  43.  
  44. private:
  45.     vector<int> v_;
  46. };
  47.  
  48. // Helpers
  49. // commutator
  50. template<int n>
  51. permutation<n>
  52. commutator(const permutation<n>& a, const permutation<n>& b) {
  53.     return a*b*a.inv()*b.inv();
  54. }
  55.  
  56. // Serialization
  57. template <int n>
  58. string asLoops(const permutation<n>& p, bool includeFixedPoints = false) {
  59.  
  60.     string res;
  61.     set<int> processed;
  62.     for (int start = 1; start <= n; ++start) {
  63.         if (processed.count(start) > 0)
  64.             continue;
  65.         if (p[start] == start && !includeFixedPoints)
  66.             continue;
  67.  
  68.         res += "(";
  69.         int cur = start;
  70.         do {
  71.             processed.insert(cur);
  72.  
  73.             res += to_string(cur);
  74.             cur = p[cur];
  75.             if (cur != start)
  76.                 res += " ";
  77.         } while (cur != start);
  78.         res += ")";
  79.     }
  80.     return res.empty() ? "id" : res;
  81. }
  82. //---------------------------------------------
  83. namespace problem15 {
  84.  
  85. typedef permutation<15> perm;
  86.  
  87. perm loop(int middle, int start) {
  88.     vector<int> v;
  89.     for (int i = start; i <= 2*middle - start; ++i)
  90.         v.push_back(i);
  91.     return perm::loop(v);
  92. }
  93.  
  94. } // ns problem15
  95.  
  96. //---------------------------------------------
  97. int main()
  98. {
  99.     namespace p15 = problem15;
  100.     set<p15::perm> generatedCmts;
  101.     int generatedCount = 0;
  102.  
  103.     for (int middle = 4; middle < 16; middle += 4)
  104.         for (int start = middle - 3; start < middle; ++start)
  105.             for (int middle2 = 4; middle2 < 16; middle2 += 4)
  106.                 for (int start2 = middle2 - 3; start2 < middle2; ++start2) {
  107.  
  108.                     p15::perm p1 = p15::loop(middle, start);
  109.                     p15::perm p2 = p15::loop(middle2, start2);
  110.  
  111.                     p15::perm cmt = commutator(p1, p2);
  112.  
  113.                     if (generatedCmts.count(cmt) > 0 || generatedCmts.count(cmt.inv()) > 0)
  114.                         continue;
  115.                     if (cmt == p15::perm::id())
  116.                         continue;
  117.                     generatedCmts.insert(cmt);
  118.                     ++generatedCount;
  119.  
  120.                     string cmtLoops = asLoops(cmt);
  121.                         if (count(cmtLoops.begin(), cmtLoops.end(), '(') == 1) // single loop
  122.                             cout << "[" << asLoops(p1) << ", " << asLoops(p2) << "] = " << asLoops(cmt) << endl;
  123.  
  124.                 }
  125. }
  126.  
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[(1 2 3 4 5 6 7), (2 3 4 5 6)] = (2 7 3)
[(1 2 3 4 5 6 7), (3 4 5)] = (3 6 4)
[(1 2 3 4 5 6 7), (7 8 9)] = (1 8 7)
[(2 3 4 5 6), (6 7 8 9 10)] = (2 7 6)
[(3 4 5), (5 6 7 8 9 10 11)] = (3 6 5)
[(5 6 7 8 9 10 11), (6 7 8 9 10)] = (6 11 7)
[(5 6 7 8 9 10 11), (7 8 9)] = (7 10 8)
[(5 6 7 8 9 10 11), (11 12 13)] = (5 12 11)
[(6 7 8 9 10), (10 11 12 13 14)] = (6 11 10)
[(7 8 9), (9 10 11 12 13 14 15)] = (7 10 9)
[(9 10 11 12 13 14 15), (10 11 12 13 14)] = (10 15 11)
[(9 10 11 12 13 14 15), (11 12 13)] = (11 14 12)
https://ideone.com/HiRWqX
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!