Xref: utzoo comp.theory:574 sci.math:10651
Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!uwm.edu!rutgers!aramis.rutgers.edu!paul.rutgers.edu!halldors
From: halldors@paul.rutgers.edu (Magnus M Halldorsson)
Newsgroups: comp.theory,sci.math
Subject: Re: efficient algorithm for generating permuations
Keywords: permutations
Message-ID: <Apr.13.12.09.47.1990.5484@paul.rutgers.edu>
Date: 13 Apr 90 16:09:48 GMT
References: <Apr.13.10.59.00.1990.217@straits.rutgers.edu>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 35

In article <Apr.13.10.59.00.1990.217@straits.rutgers.edu> majidi@straits.rutgers.edu (Masoud Majidi) writes:

> Is there an easily computable function which defines a bijection from
> numbers 1..n! to permuations of 1..n

Try this:

Input: A permutation encoded as an integer x in [0..n!-1]
Output: A permutation encoded in an array perm(1..n) such that
  perm(i) = the rank of item in the list {1,2,..,n} with
            perm(1)..perm(i-1) removed.
  (e.g. if perm(1) = 5 & perm(2) = 3, then perm(3)=4 implies that the
third element in the permutation is the one of rank four in
{1,2,4,6,7,...n}, namely '6')


  for i=1 to n-1 do
     perm(i) <- x div (n-i)!
     x <- x mod (n-i)!
  od


To convert from this format to the more conventional format, we might
use some fancy tree structure, or quick&dirty:

  for i=2 to n do
    perm2(i) = perm(i)
    for j=1 to i-1 do
      if perm(j) <= perm2(i) then
         perm2(i) <- perm2(i) - 1
    od
  od


Magnus