Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind

### 3 Permutation Encoding

A permutation $$\pi=\pi_{1} \ldots \pi_{n}$$ has rank encoding $$p_{1} \ldots p_{n}$$ where $$p_{i}= |\{j : j \geq i, \pi_{j} \leq \pi_{i} \} |$$. In other words the rank encoded permutation is a sequence of $$p_{i}$$ with $$1\leq i\leq n$$, where $$p_{i}$$ is the rank of $$\pi_{i}$$ in $$\{\pi_{i},\pi_{i+1},\ldots ,\pi_{n}\}$$. [AAR03]

The encoding of the permutation 3 2 5 1 6 7 4 8 9 is done as follows:

 Permutation Encoding Assisting list 325167489 $$\emptyset$$ 123456789 25167489 3 12456789 5167489 32 1456789 167489 323 146789 67489 3231 46789 7489 32312 4789 489 323122 489 89 3231221 89 9 32312211 9 $$\emptyset$$ 323122111 $$\emptyset$$

Decoding a permutation is done in a similar fashion, taking the sequence $$p_{1} \ldots p_{n}$$ and using the reverse process will lead to the permutation $$\pi=\pi_{1} \ldots \pi_{n}$$, where $$\pi_{i}$$ is determined by finding the number that has rank $$p_{i}$$ in $$\{\pi_{i}, \pi_{i+1}, \ldots , \pi_{n}\}$$.

The sequence 3 2 3 1 2 2 1 1 1 is decoded as:

 Encoding Permutation Assisting list 323122111 $$\emptyset$$ 123456789 23122111 3 12456789 3122111 32 1456789 122111 325 146789 22111 3251 46789 2111 32516 4789 111 325167 489 11 3251674 89 1 32516748 9 $$\emptyset$$ 325167489 $$\emptyset$$

#### 3.1 Encoding and Decoding

##### 3.1-1 RankEncoding
 ‣ RankEncoding( p ) ( function )

Returns: A list that represents the rank encoding of the permutation p.

Using the algorithm above RankEncoding turns the permutation p into a list of integers.

gap> RankEncoding([3, 2, 5, 1, 6, 7, 4, 8, 9]);
[ 3, 2, 3, 1, 2, 2, 1, 1, 1 ]
gap> RankEncoding([ 4, 2, 3, 5, 1 ]);
[ 4, 2, 2, 2, 1 ]
gap> 

##### 3.1-2 RankDecoding
 ‣ RankDecoding( e ) ( function )

Returns: A permutation in list form.

A rank encoded permutation is decoded by using the reversed process from encoding, which is also explained above.

gap> RankDecoding([ 3, 2, 3, 1, 2, 2, 1, 1, 1 ]);
[ 3, 2, 5, 1, 6, 7, 4, 8, 9 ]
gap> RankDecoding([ 4, 2, 2, 2, 1 ]);
[ 4, 2, 3, 5, 1 ]
gap> 

##### 3.1-3 SequencesToRatExp
 ‣ SequencesToRatExp( list ) ( function )

Returns: A rational expression that describes all the words in list.

A list of sequences is turned into a rational expression by concatenating each sequence and unifying all of them.

gap> SequencesToRatExp([[ 1, 1, 1, 1, 1 ],[ 2, 1, 2, 2, 1 ],[ 3, 2, 1, 2, 1 ],
> [ 4, 2, 3, 2, 1 ]]);
11111U21221U32121U42321
gap> 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind

generated by GAPDoc2HTML