Permutation Class Reference

#include <Permutation.h>

Classes
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.
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 (indices start with 0).
vector< int >	geodesicWord () const
	Find a geodesic word representing the permutation (indices start with 1).
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 $\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)

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

vector<int> Permutation::geodesic ( ) const

Find a geodesic word representing the permutation (indices start with 0).

vector<int> Permutation::geodesicWord ( ) const

Find a geodesic word representing the permutation (indices start with 1).

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

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