From: Helmut.Richter@lrz-muenchen.de (Helmut Richter)
Subject: Re: efficient way to code ordering
Date: 4 Jan 1999 10:02:59 GMT
Newsgroups: sci.math
Keywords: Enumerating permutations

Kevin P Chugh <chugh@cs.buffalo.edu> writes:

>hi- i'm looking for a space efficent way to code an ordering. if i 
>have 4 elements, and i need to store the order of the elements,
>(this is a set), an inefficient way would be to just save the order
>itself.  for example, if i have elements 0,1,2,3 and their order is
>2,1,0,3, i can just save 2,1,0,3.  A better way is to 
>find some number that encodes the order.  Since there are 4! possible
>orders, i can code the order with some number between 0 and 24, 
>which is better than using 4 digits to represent the order.  is
>there any better way to code an ordering?  a little more formally,
>i can code the ordering of an X member set inefficiently with
>X*logX space, or using the other method log(X!) space.  anything out there 
>that's better than log(X!) space?  any books on the subject? thanks
>for any help.

>kevin

To assign a number to an ordering, throw out the highest number, get
the order number, say X, of what remains, multiply by the length of
the ordering, and add where the highest number has to fit in (counting
from  right if X even and from left if X odd).

Example:

order number of 2130
  = order number of 210 (highest number "3" thrown out)
    * 4 (length of "2130")
    + distance of 3 from the proper edge

  order number of 210
    = order number of 10 (highest number "2" thrown out)
      * 3 (length of "210")
      + distance of 2 from the proper edge

    order number of 10
      = order number of 0 (highest number "1" thrown out)
        * 2 (length of "10")
        + distance of 1 from the proper edge

      order number of 0 = 0 (always)

    order number of 10
      = 0 (order number of 0)
        * 2 (length of "10")
        + 1 (distance of 1 from the right-hand edge)
      = 1

  order number of 210
    = 1 (order number of 10)
      * 3 (length of "210")
      + 0 (distance of 2 from the left-hand edge)
    = 3

order number of 2130
  = 3 (order number of 210)
    * 4 (length of "2130")
    + 2 (distance of 3 from the left-hand edge)
  = 14

Now a list of all permutations according to these rules:

     0. 0123
     1. 0132
     2. 0312
     3. 3012
     4. 3021
     5. 0321
     6. 0231
     7. 0213
     8. 2013
     9. 2031
    10. 2301
    11. 3201
    12. 3210
    13. 2310
    14. 2130
    15. 2103
    16. 1203
    17. 1230
    18. 1320
    19. 3120
    20. 3102
    21. 1302
    22. 1032
    23. 1023

The rule that the positions are counted alternatingly from right and
from  left is not necessary for the uniqueness of the numbering, but it
is very useful: so the permutation number n+1 is obtained from
permutation number n by swapping two adjacent elements. In particular,
the order number of a permutation is odd if and only if the
permutation itself is odd (that is: takes an odd number of swaps of
arbitrary elements to restore the standard ordering; or: has an odd
number of pairs of elements that are not in standard order).

Note the symmetry: the circle is closed, and the reverse string of
permutation i has number i+-(n!/2).

Helmut Richter