Permutation.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class Permutation
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
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 //----------------------------- Permutation ---------------------------------//
00022 //---------------------------------------------------------------------------//
00023 
00024 
00026 
00032 class Permutation
00033 {
00034 
00036   //                                                     //
00037   //  Constructors                                       //
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   // Permutation( const Permutation& p );
00059   
00060   
00062   static Permutation CYCLE( int N , const vector< int >& cycle );
00063   
00064   
00066   //                                                     //
00067   //  Operators:                                         //
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   // a function for fast multiplication of a permutation by cycles on the left and on the right
00116   // P = -I !!! a must
00117 
00118 
00120   //                                                     //
00121   //  Accessors:                                         //
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   // bool computeConjugator( const Permutation& p , Permutation& res ) const;
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   //  Lattice operations:                                //
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   //  I/O:                                               //
00259   //                                                     //
00261 
00262 public:
00263 
00264   friend ostream& operator << ( ostream& os , const Permutation& p );
00265 
00267   //                                                     //
00268   //  Internal functions:                                //
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   //  Data members                                       //
00298   //                                                     //
00300 
00301   friend class BraidGroup;
00302   
00303 private:
00304 
00306   vector< int > theValue;
00307 
00308 };
00309 
00310 
00311 
00312 
00313 #endif

Generated on Sun Dec 3 10:58:56 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6