対称性からの群論入門 問題 14.4 の確認

対称性からの群論入門 (Undergraduate Texts in Mathematics)

の問題で、の中で(1 2 3)(4 5 6)と(5 3 1)(2 6 4)は共役だけどの中の(1 2 3 4 5)(6 7 8)と(4 3 7 8 6)(2 1 5)は共役にならないことを示せという問題があったけど、手では解けなかったので、機械で確かめてみた。こういう全探索は、トップコーダー養成講座のおかげで、だいぶサクっと書けるようになったぁ。

#include <vector>
#include <iostream>
#include <stdexcept>
#include <algorithm>
#include <iterator>
#include <string>
#include <sstream>

using namespace std;

string trim(const string& s){
  if(s.length() == 0)
    return s;
  size_t b = s.find_first_not_of(" \t\r\n");
  size_t e = s.find_last_not_of(" \t\r\n");
  if(b == string::npos)
    return "";
  return string(s, b, e - b + 1);
}


class Permutation{
protected:
  vector<size_t> v;
  size_t n;

public:
  Permutation(const size_t n_=0)
    : v(n_), n(n_)
  {}

  size_t& operator[](const size_t i){
    return v[i];
  }

  const size_t& operator[](const size_t i) const{
    return v[i];
  }

  bool operator==(const Permutation& r){
    return v == r.v;
  }

  size_t size() const{
    return v.size();
  }
};

class CyclicPermutation : public Permutation{
public:
  CyclicPermutation(const Permutation& p)
    : Permutation(p)
  {
    cycle();
  }

  CyclicPermutation(const string& s){
    parse(s);
    size_t sum = 0;
    for(size_t i = 0; i < c.size(); i++){
      sum += c[i].size();
    }
    n = sum;
    v.resize(n);
    for(size_t i = 0; i < c.size(); i++){
      for(size_t j = 0; j < c[i].size() - 1; j++){
        v[c[i][j]] = c[i][j + 1];
      }
      v[c[i][c[i].size() - 1]] = c[i][0];
    }
  }

  string str() const {
    stringstream ret;
    for(size_t i = 0; i < c.size(); i++){
      ret << "(" << c[i][0];
      for(size_t j = 1; j < c[i].size(); j++){
        ret << " " << c[i][j];
      }
      ret << ")";
    }
    return ret.str();
  }

  bool isEven(){
    bool ret = true;
    for(size_t i = 0; i < c.size(); i++){
      if(c[i].size() % 2 == 0){
	ret = !ret;
      }
    }
    return ret;
  }

protected:
  vector<vector<size_t> > c;


  void cycle(){
    vector<bool> used(n, false);
    size_t dest;

    for(size_t i = 0; i < n; i++){
      if(!used[i]){
	used[i] = true;
	c.push_back(vector<size_t>(1, i));
	dest = v[i];
	while(!used[dest]){
	  used[dest] = true;
	  c.back().push_back(dest);
	  dest = v[dest];
	}
      }
    }
  }

  void parse(const string& str){
    string s = trim(str);
    while(s.size() > 0){
      size_t closePos = s.find_first_of(")");
      stringstream sst(s.substr(1, closePos - 1));
      size_t buf;
      c.push_back(vector<size_t>(0));
      do{
	sst >> buf;
	c.back().push_back(buf);
      } while(!sst.eof());
      s.erase(0, closePos + 1);
    }
  }
};


Permutation prod(const Permutation& l, const Permutation r){
  if(l.size() != r.size()){
    throw logic_error("Sizes of l and r are inconsistent.");
  }

  Permutation ret(l.size());
  for(size_t i = 0; i < l.size(); i++){
    ret[i] = l[r[i]];
  }

  return ret;
}

Permutation inv(const Permutation p){
  Permutation ret(p.size());

  for(size_t i = 0; i < p.size(); i++){
    ret[p[i]] = i;
  }

  return ret;
}


ostream& operator<<(ostream& ost, const Permutation& p){
  //   for(size_t i = 0; i < p.size(); i++){
  //     ost << p[i] << " ";
  //   }
  ost << "= " << CyclicPermutation(p).str();
  return ost;
}

ostream& operator<<(ostream& ost, const CyclicPermutation& p){
  //   for(size_t i = 0; i < p.size(); i++){
  //     ost << p[i] << " ";
  //   }
  ost << "= " << p.str();
  return ost;
}

class Search{
  const Permutation* const base;
  const Permutation* const obj;
  vector<bool> used;
  const size_t n;
  Permutation comp;


public:
  Search(const Permutation& base_, const Permutation& obj_)
    : base(&base_),
      obj(&obj_),     
      used(obj_.size()),
      n(obj_.size()),
      comp(obj_.size())   
  {
    if(obj->size() != base->size()){
      throw logic_error("Sizes of object and base permutation are inconsistent");
    }
    cout << "object permutation : " << *obj << endl;
    cout << "base permutation : " << *base << endl;
  }

  void run(){
    fill(used.begin(), used.end(), false);
    dfs(0);
  }

  void dfs(const size_t pos){
    if(pos == n){
      Permutation conj =
	prod(prod(comp, *base), inv(comp));
      bool check = (conj == *obj);
      bool isEven = CyclicPermutation(comp).isEven();


      cout << comp
	   << " : "
	   << (check ? "true" : "false")
	   << " : "
	   << (isEven ? "true" : "false")
	   << endl;
      return;
    }

    for(size_t i = 0; i < n; i++){
      if(!used[i]){
	used[i] = true;
	comp[pos] = i;
	dfs(pos + 1);
	used[i] = false;
      }
    }
  }
};

int main(int argc, char* argv[]){
  CyclicPermutation
    //     base("(0 1 2)(3 4 5)"),
    //     obj("(4 2 0)(1 5 3)");
    base("(0 1 2 3 4)(5 6 7)"),
    obj("(3 2 6 7 5)(1 0 4)");


  Search s(base, obj);
  s.run();
}