Permutation Class Reference

Permutation. More...

#include <Permutation.h>

List of all members.

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 $\Delta$).
Permutation tinyFlip (int sh) const
 Perform a tiny flip (conjugate by $\delta$).
bool isTrivial () const
 Check if the permutation is trivial.
vector< int > geodesic () const
 Find a geodesic word representing the permutation.
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)
 What is it?
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 $\Delta = (n-1,n-2,\ldots,2,1,0)$.
static Permutation getCyclePermutation (int size)
 Get half twist permutation $\Delta = (1,2,\ldots,n-2,n-1,0)$.
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)

Classes

struct  triple


Detailed Description

Permutation.

We use the standard representation of a presentation on $n$ symbols - a sequence of numbers $( x_0, \ldots, x_{n-1} )$. Notice that indexes start at 0.

Definition at line 32 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 54 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 129 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]
 

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 $\Delta$).

vector<int> Permutation::geodesic  )  const
 

Find a geodesic word representing the permutation.

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

Get half twist permutation $\Delta = (1,2,\ldots,n-2,n-1,0)$.

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

Get half twist permutation $\Delta = (n-1,n-2,\ldots,2,1,0)$.

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 133 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 $p_1$ and $p_2$ be two permutations. The maximal permutation $P$ which ends $p_1$ and $p_2$ is called the left greatest common divisor of $p_1$ and $p_2$, i.e., $P$ is maximal such that $p_1 = P \circ d_1 $ and $p_2 = P \circ d_1 $ for some permutations $d_1$ and $d_2$.

Permutation Permutation::LeftLCM const Permutation p  )  const
 

Compute LeftLCM of 2 permutations.

Let $p_1$ and $p_2$ be two permutations. The minimal permutation $P$ which starts with $p_1$ and $p_2$ is called the left least common multiple, i.e., $P$ is minimal such that $P = p_1 \circ d_1 $ and $P = p_2 \circ d_2 $ .

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).

Permutation Permutation::operator * const Permutation p  )  const
 

Multiple 2 permutations.

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

Multiple 1 permutation by another on the right.

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

Check if 2 permutations are not equal.

Permutation Permutation::operator-  )  const [inline]
 

Invert the permutation.

Definition at line 102 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 79 of file Permutation.h.

References theValue.

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

Get the ith element of the permutation.

Definition at line 75 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 $p_1$ and $p_2$ be two permutations. The maximal permutation $P$ which ends $p_1$ and $p_2$ is called the right greatest common divisor of $p_1$ and $p_2$, i.e., $P$ is maximal such that $p_1 = d_1 \circ P $ and $p_2 = d_2 \circ P $ for some permutations $d_1$ and $d_2$.

Permutation Permutation::RightLCM const Permutation p  )  const
 

Compute RightLCM of 2 permutations.

Let $p_1$ and $p_2$ be two permutations. The minimal permutation $P$ which ends with $p_1$ and $p_2$ is called the right least common multiple, i.e., $P$ is minimal such that $P = d_1 \circ p_1 $ and $P = d_2 \circ p_2 $ .

int Permutation::size  )  const [inline]
 

Get the size of the permutation.

Definition at line 141 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 $\delta$).


Friends And Related Function Documentation

friend class BraidGroup [friend]
 

Definition at line 301 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 306 of file Permutation.h.

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


The documentation for this class was generated from the following file:
Generated on Sun Dec 3 10:59:02 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6