00001
00002 #ifndef _Permutation_h_
00003 #define _Permutation_h_
00004
00005 #include "set"
00006 #include "map"
00007 #include "vector"
00008
00009 using namespace std;
00010
00011
00012
00013
00014
00015 class Permutation
00016 {
00017
00019
00020
00021
00023
00024 public:
00025
00026 Permutation( int l=0 );
00027 Permutation( int size , const int* p );
00028 Permutation( const vector< int >& p );
00029
00030
00031 static Permutation CYCLE( int N , const vector< int >& cycle );
00032
00034
00035
00036
00038
00039 public:
00040
00041 int operator[] ( int ind ) const { return theValue[ind]; }
00042 int& operator[] ( int ind ) { return theValue[ind]; }
00043
00044 bool operator == ( const Permutation& p ) const;
00045 bool operator != ( const Permutation& p ) const;
00046 bool operator < ( const Permutation& p ) const;
00047 Permutation operator * ( const Permutation& p ) const;
00048 Permutation& operator *= ( const Permutation& p );
00049 Permutation operator - ( ) const { return inverse( ); }
00050 Permutation inverse( ) const;
00051
00052 Permutation& left_mult_by_cycle( const vector< int >& cycle );
00053 static void lr_multiply_by_cycles( Permutation& P , Permutation& I , const vector< int >& M1 , const vector< int >& M2 );
00054
00055
00056
00057
00059
00060
00061
00063
00064 public:
00065
00066 void change( int i , int j ) { swap( theValue[i] , theValue[j] ); }
00067
00068 const vector< int >& getVector( ) const { return theValue; }
00069 Permutation power( int p ) const;
00070
00071 int size( ) const { return theValue.size( ); }
00072 int difference( const Permutation& p ) const;
00073
00074 Permutation computeConjugacyClassRepresentative( Permutation& conj ) const;
00075 Permutation computeConjugator( const Permutation& p ) const;
00076
00077
00078
00079 static Permutation random( int l );
00080
00081 Permutation meet( const Permutation& p ) const;
00082
00083 Permutation meet2( const Permutation& p ) const;
00084 Permutation join2( const Permutation& p ) const;
00085
00086
00087
00088 static bool mixable( const Permutation& p1 , const Permutation& p2 );
00089
00090 bool isTrivial( ) const;
00091
00092 vector<int> geodesic( ) const;
00093 vector<int> getWordPresentation( ) const;
00094
00095
00096
00097 Permutation tinyFlip( int sh ) const;
00098
00099
00100
00102
00103
00104
00106
00107 public:
00108
00109 friend ostream& operator << ( ostream& os , const Permutation& p );
00110
00112
00113
00114
00116
00117 private:
00118
00119 void _sub_meet( const Permutation& p ,
00120 const Permutation& ip1 ,
00121 const Permutation& ip2 ,
00122 Permutation& cur ,
00123 int* left_indeces_a ,
00124 int* left_indeces_b ,
00125 int* right_indeces_a ,
00126 int* right_indeces_b ,
00127 int beg , int end ) const;
00128
00129
00130 struct triple {
00131 triple( int p1=0 , int p2=0 , int p3=0 ) : c1(p1), c2(p2), c3(p3) { }
00132 int c1, c2, c3;
00133 };
00134
00135 void prepare_pairs( int N,
00136 Permutation& P,
00137 vector< pair<int,int> >& pairs ) const;
00138
00140
00141
00142
00144
00145 friend class BraidGroup;
00146
00147 private:
00148
00149 vector< int > theValue;
00150
00151 };
00152
00153
00154
00155
00156 #endif