Permutation.h

Go to the documentation of this file.
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 //----------------------------- Permutation ---------------------------------//
00013 //---------------------------------------------------------------------------//
00014 
00015 class Permutation
00016 {
00017 
00019   //                                                     //
00020   //  Constructors                                       //
00021   //                                                     //
00023   
00024 public:
00025   
00026   Permutation( int l=0 );
00027   Permutation( int size , const int* p );
00028   Permutation( const vector< int >& p );
00029   // Permutation( const Permutation& p );
00030 
00031         static Permutation CYCLE( int N , const vector< int >& cycle );
00032 
00034   //                                                     //
00035   //  Operators:                                         //
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         // a function for fast multiplication of a permutation by cycles on the left and on the right
00055         // P = -I !!! a must
00056 
00057 
00059   //                                                     //
00060   //  Accessors:                                         //
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   // bool computeConjugator( const Permutation& p , Permutation& res ) const;
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   // operations designed for parallel descending cycles
00086   // for other permutations it makes no sense
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   // operation designed for parallel descending cycles
00095   // for other permutations it makes no sense
00096 
00097   Permutation tinyFlip( int sh ) const;
00098   // the result of a conjugation by a tiny flip
00099   // sigma^-1 * Permutation * sigma
00100 
00102   //                                                     //
00103   //  I/O:                                               //
00104   //                                                     //
00106   
00107 public:
00108 
00109   friend ostream& operator << ( ostream& os , const Permutation& p );
00110 
00112   //                                                     //
00113   //  Internal functions:                                //
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   //  Data members                                       //
00142   //                                                     //
00144 
00145   friend class BraidGroup;
00146   
00147 private:
00148 
00149   vector< int > theValue;
00150 
00151 };
00152 
00153 
00154 
00155 
00156 #endif

Generated on Mon Feb 27 22:47:04 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.4