00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #ifndef _Permutation_h_
00011 #define _Permutation_h_
00012
00013 #include "set"
00014 #include "map"
00015 #include "vector"
00016
00017 using namespace std;
00018
00019
00020
00021
00022
00023
00024
00026
00032 class Permutation
00033 {
00034
00036
00037
00038
00040
00041 public:
00042
00044 Permutation( int size=0 );
00045
00047 Permutation( int size , const int* p );
00048
00050 Permutation( const vector< int >& p );
00051
00052
00054 template< class IntIterator > Permutation( const IntIterator& B , const IntIterator& E ) : theValue( B , E ) { }
00055
00056
00058
00059
00060
00062 static Permutation CYCLE( int N , const vector< int >& cycle );
00063
00064
00066
00067
00068
00070
00071 public:
00072
00073
00075 int operator[] ( int ind ) const { return theValue[ind]; }
00076
00077
00079 int& operator[] ( int ind ) { return theValue[ind]; }
00080
00082 bool operator == ( const Permutation& p ) const;
00083
00084
00086 bool operator != ( const Permutation& p ) const;
00087
00088
00090 bool operator < ( const Permutation& p ) const;
00091
00092
00094 Permutation operator * ( const Permutation& p ) const;
00095
00096
00098 Permutation& operator *= ( const Permutation& p );
00099
00100
00102 Permutation operator - ( ) const { return inverse( ); }
00103
00104
00106 Permutation inverse( ) const;
00107
00108
00110 Permutation& left_mult_by_cycle( const vector< int >& cycle );
00111
00112
00114 static void lr_multiply_by_cycles( Permutation& P , Permutation& I , const vector< int >& M1 , const vector< int >& M2 );
00115
00116
00117
00118
00120
00121
00122
00124
00125 public:
00126
00127
00129 void change( int i , int j ) { swap( theValue[i] , theValue[j] ); }
00130
00131
00133 const vector< int >& getVector( ) const { return theValue; }
00134
00135
00137 Permutation power( int p ) const;
00138
00139
00141 int size( ) const { return theValue.size( ); }
00142
00144 Permutation increaseSize( int N ) const;
00145
00146
00148 int length( ) const;
00149
00150
00152 int difference( const Permutation& p ) const;
00153
00154
00156 Permutation computeConjugacyClassRepresentative( Permutation& conj ) const;
00157
00158
00160 Permutation computeConjugator( const Permutation& p ) const;
00161
00162
00163
00165 Permutation flip( ) const;
00166
00167
00169 Permutation tinyFlip( int sh ) const;
00170
00171
00173 static Permutation random( int size );
00174
00175
00177 static Permutation getHalfTwistPermutation( int size );
00178
00179
00181 static Permutation getCyclePermutation( int size );
00182
00183
00185 static bool mixable( const Permutation& p1 , const Permutation& p2 );
00186
00187
00189 bool isTrivial( ) const;
00190
00191
00193 vector<int> geodesic( ) const;
00194
00195
00197 vector< int > getWordPresentation( ) const;
00198
00199
00201
00202
00203
00205
00206 public:
00207
00209
00215 Permutation RightGCD( const Permutation& p ) const;
00216
00217
00219
00225 Permutation RightLCM( const Permutation& p ) const;
00226
00227
00229
00235 Permutation LeftGCD( const Permutation& p ) const;
00236
00237
00239
00245 Permutation LeftLCM( const Permutation& p ) const;
00246
00247
00249 Permutation meet2( const Permutation& p ) const;
00250
00251
00253 Permutation join2( const Permutation& p ) const;
00254
00255
00257
00258
00259
00261
00262 public:
00263
00264 friend ostream& operator << ( ostream& os , const Permutation& p );
00265
00267
00268
00269
00271
00272 private:
00273
00275 void _sub_meet( const Permutation& p ,
00276 const Permutation& ip1 ,
00277 const Permutation& ip2 ,
00278 Permutation& cur ,
00279 int* left_indeces_a ,
00280 int* left_indeces_b ,
00281 int* right_indeces_a ,
00282 int* right_indeces_b ,
00283 int beg , int end ) const;
00284
00285
00286 struct triple {
00287 triple( int p1=0 , int p2=0 , int p3=0 ) : c1(p1), c2(p2), c3(p3) { }
00288 int c1, c2, c3;
00289 };
00290
00291 void prepare_pairs( int N,
00292 Permutation& P,
00293 vector< pair<int,int> >& pairs ) const;
00294
00296
00297
00298
00300
00301 friend class BraidGroup;
00302
00303 private:
00304
00306 vector< int > theValue;
00307
00308 };
00309
00310
00311
00312
00313 #endif