Permutation.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexander Ushakov
// Contents: Definition of class Permutation
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//


#ifndef _Permutation_h_
#define _Permutation_h_

#include <set>
#include <map>
#include <vector>
#include <iostream>

using namespace std;


//---------------------------------------------------------------------------//
//----------------------------- Permutation ---------------------------------//
//---------------------------------------------------------------------------//



class Permutation
{

  //                                                     //
  //  Constructors                                       //
  //                                                     //
  
public:
  
  Permutation( int size=0 );
  
  Permutation( int size , const int* p );

  Permutation( const vector< int >& p );
  

  template< class IntIterator > Permutation( const IntIterator& B , const IntIterator& E ) : theValue( B , E ) { }

  
  // Permutation( const Permutation& p );
  
  
  static Permutation CYCLE( int N , const vector< int >& cycle );
  
  
  //                                                     //
  //  Operators:                                         //
  //                                                     //
  
public:

  
  int  operator[] ( int ind ) const { return theValue[ind]; }
  
  
  int& operator[] ( int ind ) { return theValue[ind]; }

  bool operator == ( const Permutation& p ) const;


  bool operator != ( const Permutation& p ) const;
  
  
  bool operator < ( const Permutation& p ) const;


  Permutation  operator *  ( const Permutation& p ) const;


  Permutation& operator *= ( const Permutation& p );


  Permutation operator - ( ) const { return inverse( ); }


  Permutation inverse( ) const;


  Permutation& left_mult_by_cycle( const vector< int >& cycle );


  static void lr_multiply_by_cycles( Permutation& P , Permutation& I , const vector< int >& M1 , const vector< int >& M2 );
  // a function for fast multiplication of a permutation by cycles on the left and on the right
  // P = -I !!! a must


  //                                                     //
  //  Accessors:                                         //
  //                                                     //
  
public:
  
  
  void change( int i , int j ) { swap( theValue[i] , theValue[j] ); }

  
  const vector< int >& getVector( ) const { return theValue; }


  Permutation power( int p ) const;
  

  int size( ) const { return theValue.size( ); }
  
  Permutation increaseSize( int N ) const;
  
  
  int length( ) const;


  int difference( const Permutation& p ) const;

  
  Permutation computeConjugacyClassRepresentative( Permutation& conj ) const;


  Permutation computeConjugator( const Permutation& p ) const;
  // bool computeConjugator( const Permutation& p , Permutation& res ) const;
  
  
  Permutation flip( ) const;
  
  
  Permutation tinyFlip( int sh ) const;
  
  
  static Permutation random( int size );
  
  
  static Permutation getHalfTwistPermutation( int size );
  static Permutation getCyclePermutation( int size );
  
  
  static bool mixable( const Permutation& p1 , const Permutation& p2 );
  

  bool isTrivial( ) const;


  vector<int> geodesic( ) const;

  vector<int> geodesicWord( ) const;

  
  vector< int > getWordPresentation( ) const;
  
  
  //                                                     //
  //  Lattice operations:                                //
  //                                                     //
  
public:
  

  Permutation RightGCD( const Permutation& p ) const;
  
  

  Permutation RightLCM( const Permutation& p ) const;
  
  

  Permutation LeftGCD( const Permutation& p ) const;
  
  

  Permutation LeftLCM( const Permutation& p ) const;
  
  
  Permutation meet2( const Permutation& p ) const;
  
  
  Permutation join2( const Permutation& p ) const;
  

  //                                                     //
  //  I/O:                                               //
  //                                                     //

public:

  friend ostream& operator << ( ostream& os , const Permutation& p );

  //                                                     //
  //  Internal functions:                                //
  //                                                     //
  
private:
  
  void _sub_meet( const Permutation& p , 
                  const Permutation& ip1 ,
                  const Permutation& ip2 ,
                  Permutation& cur , 
                  int* left_indeces_a ,
                  int* left_indeces_b ,
                  int* right_indeces_a ,
                  int* right_indeces_b ,
                  int beg , int end ) const;


  struct triple {
    triple( int p1=0 , int p2=0 , int p3=0 ) : c1(p1), c2(p2), c3(p3) { }
    int c1, c2, c3;
  };
  
  void prepare_pairs( int N, 
                      Permutation& P, 
                      vector< pair<int,int> >& pairs ) const;
 
  //                                                     //
  //  Data members                                       //
  //                                                     //

  friend class BraidGroup;
  
private:

  vector< int > theValue;

};




#endif