Permutation Class Reference

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

Permutation & operator *= (const Permutation &p)

Multiple 1 permutation by another on the right.

Permutation operator- () const

Invert the permutation.

Permutation inverse () const

Invert the permutation.

Permutation & left_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:

general/include/Permutation.h

Generated on Sun Dec 3 10:59:02 2006 for CRyptography And Groups (CRAG) by

1.4.6


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.
Permutation &	operator *= (const Permutation &p)
	Multiple 1 permutation by another on the right.
Permutation	operator- () const
	Invert the permutation.
Permutation	inverse () const
	Invert the permutation.
Permutation &	left_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