Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

3 Permutation Encoding
 3.1 Encoding and Decoding

3 Permutation Encoding

A permutation π=π_1 ... π_n has rank encoding p_1 ... p_n where p_i= |{j : j ≥ i, π_j ≤ π_i } |. In other words the rank encoded permutation is a sequence of p_i with 1≤ i≤ n, where p_i is the rank of π_i in {π_i,π_i+1,... ,π_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 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
323122111

 


Decoding a permutation is done in a similar fashion, taking the sequence p_1 ... p_n and using the reverse process will lead to the permutation π=π_1 ... π_n, where π_i is determined by finding the number that has rank p_i in {π_i, π_i+1, ... , π_n}.

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

Encoding Permutation Assisting list
323122111 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
325167489

 


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> 
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind

generated by GAPDoc2HTML