Xref: utzoo comp.theory:575 sci.math:10655
Path: utzoo!attcan!uunet!cs.utexas.edu!uwm.edu!psuvax1!shire!berman
From: berman@shire.cs.psu.edu (Piotr Berman)
Newsgroups: comp.theory,sci.math
Subject: Re: efficient algorithm for generating permuations
Keywords: permutations
Message-ID: <E*01qs5@cs.psu.edu>
Date: 13 Apr 90 18:49:54 GMT
References: <Apr.13.10.59.00.1990.217@straits.rutgers.edu>
Sender: news@cs.psu.edu (Usenet)
Organization: Penn State University Computer Science
Lines: 20

In article <Apr.13.10.59.00.1990.217@straits.rutgers.edu> majidi@straits.rutgers.edu (Masoud Majidi) writes:
>
>I am looking for an efficient algorithm to solve the following
>problem:
>
>Is there an easily computable function which defines a bijection from
>numbers 1..n! to permuations of 1..n
>
One can view a permutation of 1..n as a sequence of numbers a[i],...,a[n]
where a[i] is in the range 0..(i-1).  The sequence itself can be coded
as sum from i=1 to n a[i]*i!  (the range of this code is 0..n!-1), decoding
is easy.
Translating a sequence: initially all places from 1 to n are unoccupied,
	                 for i=n downto 1 do
			     put i in (a[i]+1)st unoccupied place
Translating a permutation: a[i] = #{j<i : p(j)<p(i)}

May be, one can provide a faster bijection, but this one is very natural.

Piotr Berman