chap3.txt

  
  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}. [2]
  
  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.
  
    Example  
    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.
  
    Example  
    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.
  
    Example  
    gap> SequencesToRatExp([[ 1, 1, 1, 1, 1 ],[ 2, 1, 2, 2, 1 ],[ 3, 2, 1, 2, 1 ],
    > [ 4, 2, 3, 2, 1 ]]);
    11111U21221U32121U42321
    gap>