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 #include <iostream>
00017 
00018 using namespace std;
00019 
00020 
00021 //---------------------------------------------------------------------------//
00022 //----------------------------- Permutation ---------------------------------//
00023 //---------------------------------------------------------------------------//
00024 
00025 
00027 
00033 class Permutation
00034 {
00035 
00037   //                                                     //
00038   //  Constructors                                       //
00039   //                                                     //
00041   
00042 public:
00043   
00045   Permutation( int size=0 );
00046   
00048   Permutation( int size , const int* p );
00049 
00051   Permutation( const vector< int >& p );
00052   
00053 
00055   template< class IntIterator > Permutation( const IntIterator& B , const IntIterator& E ) : theValue( B , E ) { }
00056 
00057   
00059   // Permutation( const Permutation& p );
00060   
00061   
00063   static Permutation CYCLE( int N , const vector< int >& cycle );
00064   
00065   
00067   //                                                     //
00068   //  Operators:                                         //
00069   //                                                     //
00071   
00072 public:
00073 
00074   
00076   int  operator[] ( int ind ) const { return theValue[ind]; }
00077   
00078   
00080   int& operator[] ( int ind ) { return theValue[ind]; }
00081 
00083   bool operator == ( const Permutation& p ) const;
00084 
00085 
00087   bool operator != ( const Permutation& p ) const;
00088   
00089   
00091   bool operator < ( const Permutation& p ) const;
00092 
00093 
00095   Permutation  operator *  ( const Permutation& p ) const;
00096 
00097 
00099   Permutation& operator *= ( const Permutation& p );
00100 
00101 
00103   Permutation operator - ( ) const { return inverse( ); }
00104 
00105 
00107   Permutation inverse( ) const;
00108 
00109 
00111   Permutation& left_mult_by_cycle( const vector< int >& cycle );
00112 
00113 
00115   static void lr_multiply_by_cycles( Permutation& P , Permutation& I , const vector< int >& M1 , const vector< int >& M2 );
00116   // a function for fast multiplication of a permutation by cycles on the left and on the right
00117   // P = -I !!! a must
00118 
00119 
00121   //                                                     //
00122   //  Accessors:                                         //
00123   //                                                     //
00125   
00126 public:
00127   
00128   
00130   void change( int i , int j ) { swap( theValue[i] , theValue[j] ); }
00131 
00132   
00134   const vector< int >& getVector( ) const { return theValue; }
00135 
00136 
00138   Permutation power( int p ) const;
00139   
00140 
00142   int size( ) const { return theValue.size( ); }
00143   
00145   Permutation increaseSize( int N ) const;
00146   
00147   
00149   int length( ) const;
00150 
00151 
00153   int difference( const Permutation& p ) const;
00154 
00155   
00157   Permutation computeConjugacyClassRepresentative( Permutation& conj ) const;
00158 
00159 
00161   Permutation computeConjugator( const Permutation& p ) const;
00162   // bool computeConjugator( const Permutation& p , Permutation& res ) const;
00163   
00164   
00166   Permutation flip( ) const;
00167   
00168   
00170   Permutation tinyFlip( int sh ) const;
00171   
00172   
00174   static Permutation random( int size );
00175   
00176   
00178   static Permutation getHalfTwistPermutation( int size );
00180   static Permutation getCyclePermutation( int size );
00181   
00182   
00184   static bool mixable( const Permutation& p1 , const Permutation& p2 );
00185   
00186 
00188   bool isTrivial( ) const;
00189 
00190 
00192   vector<int> geodesic( ) const;
00193 
00195   vector<int> geodesicWord( ) const;
00196 
00197   
00199   vector< int > getWordPresentation( ) const;
00200   
00201   
00203   //                                                     //
00204   //  Lattice operations:                                //
00205   //                                                     //
00207   
00208 public:
00209   
00211 
00217   Permutation RightGCD( const Permutation& p ) const;
00218   
00219   
00221 
00227   Permutation RightLCM( const Permutation& p ) const;
00228   
00229   
00231 
00237   Permutation LeftGCD( const Permutation& p ) const;
00238   
00239   
00241 
00247   Permutation LeftLCM( const Permutation& p ) const;
00248   
00249   
00251   Permutation meet2( const Permutation& p ) const;
00252   
00253   
00255   Permutation join2( const Permutation& p ) const;
00256   
00257 
00259   //                                                     //
00260   //  I/O:                                               //
00261   //                                                     //
00263 
00264 public:
00265 
00266   friend ostream& operator << ( ostream& os , const Permutation& p );
00267 
00269   //                                                     //
00270   //  Internal functions:                                //
00271   //                                                     //
00273   
00274 private:
00275   
00277   void _sub_meet( const Permutation& p , 
00278                   const Permutation& ip1 ,
00279                   const Permutation& ip2 ,
00280                   Permutation& cur , 
00281                   int* left_indeces_a ,
00282                   int* left_indeces_b ,
00283                   int* right_indeces_a ,
00284                   int* right_indeces_b ,
00285                   int beg , int end ) const;
00286 
00287 
00288   struct triple {
00289     triple( int p1=0 , int p2=0 , int p3=0 ) : c1(p1), c2(p2), c3(p3) { }
00290     int c1, c2, c3;
00291   };
00292   
00293   void prepare_pairs( int N, 
00294                       Permutation& P, 
00295                       vector< pair<int,int> >& pairs ) const;
00296  
00298   //                                                     //
00299   //  Data members                                       //
00300   //                                                     //
00302 
00303   friend class BraidGroup;
00304   
00305 private:
00306 
00308   vector< int > theValue;
00309 
00310 };
00311 
00312 
00313 
00314 
00315 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:45 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1