# Permutation Class Reference

#include <Permutation.h>

List of all members.

struct  triple

## Public Member Functions

Permutation (int size=0)
Default constructor (size specifies the size of the permutation).
Permutation (int size, const int *p)
Construct a permutation of the specified size given by the array p.
Permutation (const vector< int > &p)
Construct a permutation by a vector of numbers.
template<class IntIterator >
Permutation (const IntIterator &B, const IntIterator &E)
Construct a permutation by a sequence of numbers.
int operator[] (int ind) const
Get the ith element of the permutation.
int & operator[] (int ind)
Get the reference to the ith element of the permutation.
bool operator== (const Permutation &p) const
Check if 2 permutations are equal.
bool operator!= (const Permutation &p) const
Check if 2 permutations are not equal.
bool operator< (const Permutation &p) const
Check if *this is strictly less than p (compared lexicographically).
Permutation operator* (const Permutation &p) const
Multiple 2 permutations.
Permutationoperator*= (const Permutation &p)
Multiple 1 permutation by another on the right.
Permutation operator- () const
Invert the permutation.
Permutation inverse () const
Invert the permutation.
Permutationleft_mult_by_cycle (const vector< int > &cycle)
A function used for computation of BKL normal forms of braids.
void change (int i, int j)
Swap the values at uth and jth position (multiply this by a cycle (i,j) on the left).
const vector< int > & getVector () const
Get the vector of numbers which represents the permutation.
Permutation power (int p) const
Raise the permutation into the power p.
int size () const
Get the size of the permutation.
Permutation increaseSize (int N) const
Increase the size of a permutation.
int length () const
Compute the length of a permutation (length of a geodesic). Current version is slow, need to update.
int difference (const Permutation &p) const
Compute the number of positions with different elements.
Permutation computeConjugacyClassRepresentative (Permutation &conj) const
Compute the conjugacy class representative (2 elements conjugate iff they have the same result of this function).
Permutation computeConjugator (const Permutation &p) const
Compute a conjugator for a couple of permutations (if permutations are not conjugate then the result makes no sense).
Permutation flip () const
Flip the permutation (conjugate by a half-twist permutation ).
Permutation tinyFlip (int sh) const
Perform a tiny flip (conjugate by ).
bool isTrivial () const
Check if the permutation is trivial.
vector< int > geodesic () const
vector< int > geodesicWord () const
vector< int > getWordPresentation () const
Compute the word presentation for a permutation which is "parallel descending cycles" (for other permutations it makes no sense).
Permutation RightGCD (const Permutation &p) const
Compute RightGCD of 2 permutations.
Permutation RightLCM (const Permutation &p) const
Compute RightLCM of 2 permutations.
Permutation LeftGCD (const Permutation &p) const
Compute LeftGCD of 2 permutations.
Permutation LeftLCM (const Permutation &p) const
Compute LeftLCM of 2 permutations.
Permutation meet2 (const Permutation &p) const
Compute GCD for 2 permutations that are "parallel descending cycles" (used for BKL Normal Forms of braids).
Permutation join2 (const Permutation &p) const
Compute LCM for 2 permutations that are "parallel descending cycles" (used for BKL Normal Forms of braids).

## Static Public Member Functions

static Permutation CYCLE (int N, const vector< int > &cycle)
Copy constructor provided by compiler.
static void lr_multiply_by_cycles (Permutation &P, Permutation &I, const vector< int > &M1, const vector< int > &M2)
A function used for computation of BKL normal forms of braids.
static Permutation random (int size)
Generate a random permutation of specified size.
static Permutation getHalfTwistPermutation (int size)
Get half twist permutation .
static Permutation getCyclePermutation (int size)
Get half twist permutation .
static bool mixable (const Permutation &p1, const Permutation &p2)
Check if 2 permutations are mixable (it is not used anywhere in the system, god knows that means).

## Private Member Functions

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
(Aux) The main operation to compute RightGCD and all other lattice functions
void prepare_pairs (int N, Permutation &P, vector< pair< int, int > > &pairs) const

## Private Attributes

vector< int > theValue
A vector representing the permutation.

## Friends

class BraidGroup
ostream & operator<< (ostream &os, const Permutation &p)

## Detailed Description

We use the standard representation of a presentation on symbols - a sequence of numbers . Notice that indexes start at 0.

Definition at line 33 of file Permutation.h.

## Constructor & Destructor Documentation

 Permutation::Permutation ( int size = 0 )

Default constructor (size specifies the size of the permutation).

 Permutation::Permutation ( int size, const int * p )

Construct a permutation of the specified size given by the array p.

 Permutation::Permutation ( const vector< int > & p )

Construct a permutation by a vector of numbers.

template<class IntIterator >
 Permutation::Permutation ( const IntIterator & B, const IntIterator & E )  [inline]

Construct a permutation by a sequence of numbers.

Definition at line 55 of file Permutation.h.

## Member Function Documentation

 void Permutation::_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 [private]

(Aux) The main operation to compute RightGCD and all other lattice functions

 void Permutation::change ( int i, int j )  [inline]

Swap the values at uth and jth position (multiply this by a cycle (i,j) on the left).

Definition at line 130 of file Permutation.h.

References theValue.

 Permutation Permutation::computeConjugacyClassRepresentative ( Permutation & conj ) const

Compute the conjugacy class representative (2 elements conjugate iff they have the same result of this function).

 Permutation Permutation::computeConjugator ( const Permutation & p ) const

Compute a conjugator for a couple of permutations (if permutations are not conjugate then the result makes no sense).

 static Permutation Permutation::CYCLE ( int N, const vector< int > & cycle )  [static]

Copy constructor provided by compiler.

What is it?

 int Permutation::difference ( const Permutation & p ) const

Compute the number of positions with different elements.

 Permutation Permutation::flip ( ) const

Flip the permutation (conjugate by a half-twist permutation ).

 vector Permutation::geodesic ( ) const

 vector Permutation::geodesicWord ( ) const

 static Permutation Permutation::getCyclePermutation ( int size )  [static]

Get half twist permutation .

 static Permutation Permutation::getHalfTwistPermutation ( int size )  [static]

Get half twist permutation .

Referenced by ThLeftNormalForm::ThLeftNormalForm(), and ThRightNormalForm::ThRightNormalForm().

 const vector< int >& Permutation::getVector ( ) const [inline]

Get the vector of numbers which represents the permutation.

Definition at line 134 of file Permutation.h.

References theValue.

 vector< int > Permutation::getWordPresentation ( ) const

Compute the word presentation for a permutation which is "parallel descending cycles" (for other permutations it makes no sense).

 Permutation Permutation::increaseSize ( int N ) const

Increase the size of a permutation.

 Permutation Permutation::inverse ( ) const

Invert the permutation.

Referenced by operator-().

 bool Permutation::isTrivial ( ) const

Check if the permutation is trivial.

Referenced by ThLeftNormalForm::ThLeftNormalForm(), and ThRightNormalForm::ThRightNormalForm().

 Permutation Permutation::join2 ( const Permutation & p ) const

Compute LCM for 2 permutations that are "parallel descending cycles" (used for BKL Normal Forms of braids).

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

A function used for computation of BKL normal forms of braids.

 Permutation Permutation::LeftGCD ( const Permutation & p ) const

Compute LeftGCD of 2 permutations.

Let and be two permutations. The maximal permutation which ends and is called the left greatest common divisor of and , i.e., is maximal such that and for some permutations and .

 Permutation Permutation::LeftLCM ( const Permutation & p ) const

Compute LeftLCM of 2 permutations.

Let and be two permutations. The minimal permutation which starts with and is called the left least common multiple, i.e., is minimal such that and .

 int Permutation::length ( ) const

Compute the length of a permutation (length of a geodesic). Current version is slow, need to update.

 static void Permutation::lr_multiply_by_cycles ( Permutation & P, Permutation & I, const vector< int > & M1, const vector< int > & M2 )  [static]

A function used for computation of BKL normal forms of braids.

 Permutation Permutation::meet2 ( const Permutation & p ) const

Compute GCD for 2 permutations that are "parallel descending cycles" (used for BKL Normal Forms of braids).

 static bool Permutation::mixable ( const Permutation & p1, const Permutation & p2 )  [static]

Check if 2 permutations are mixable (it is not used anywhere in the system, god knows that means).

 bool Permutation::operator!= ( const Permutation & p ) const

Check if 2 permutations are not equal.

 Permutation Permutation::operator* ( const Permutation & p ) const

Multiple 2 permutations.

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

Multiple 1 permutation by another on the right.

 Permutation Permutation::operator- ( ) const [inline]

Invert the permutation.

Definition at line 103 of file Permutation.h.

References inverse().

 bool Permutation::operator< ( const Permutation & p ) const

Check if *this is strictly less than p (compared lexicographically).

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

Check if 2 permutations are equal.

 int& Permutation::operator[] ( int ind )  [inline]

Get the reference to the ith element of the permutation.

Definition at line 80 of file Permutation.h.

References theValue.

 int Permutation::operator[] ( int ind ) const [inline]

Get the ith element of the permutation.

Definition at line 76 of file Permutation.h.

References theValue.

 Permutation Permutation::power ( int p ) const

Raise the permutation into the power p.

 void Permutation::prepare_pairs ( int N, Permutation & P, vector< pair< int, int > > & pairs ) const [private]
 static Permutation Permutation::random ( int size )  [static]

Generate a random permutation of specified size.

 Permutation Permutation::RightGCD ( const Permutation & p ) const

Compute RightGCD of 2 permutations.

Let and be two permutations. The maximal permutation which ends and is called the right greatest common divisor of and , i.e., is maximal such that and for some permutations and .

 Permutation Permutation::RightLCM ( const Permutation & p ) const

Compute RightLCM of 2 permutations.

Let and be two permutations. The minimal permutation which ends with and is called the right least common multiple, i.e., is minimal such that and .

 int Permutation::size ( ) const [inline]

Get the size of the permutation.

Definition at line 142 of file Permutation.h.

References theValue.

Referenced by ThLeftNormalForm::ThLeftNormalForm(), and ThRightNormalForm::ThRightNormalForm().

 Permutation Permutation::tinyFlip ( int sh ) const

Perform a tiny flip (conjugate by ).

## Friends And Related Function Documentation

 friend class BraidGroup [friend]

Definition at line 303 of file Permutation.h.

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

## Member Data Documentation

 vector< int > Permutation::theValue [private]

A vector representing the permutation.

Definition at line 308 of file Permutation.h.

Referenced by change(), getVector(), operator[](), and size().

The documentation for this class was generated from the following file:

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