majidi@straits.rutgers.edu (Masoud Majidi) (04/13/90)
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 I can easily write a function that generates all the permuations but I don't know of any algorithm which would give a permutation without generating exponentially many permutations. I would appreciate any help. Masoud Majidi(majidi@paul.rutgers.edu)
halldors@paul.rutgers.edu (Magnus M Halldorsson) (04/13/90)
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
edp@jareth.enet.dec.com (Always mount a scratch monkey.) (04/14/90)
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 I will describe such a function. It uses a number of division/remainder operations, but it does what you ask for above fairly easily. However, if you want to generate sequences of permutations, not just one, then there are better algorithsm, such as one that generates each possible permutation by exchange only a single pair at a time. I will use 0 as a base, not 1 as you have above. Let the elements to permute be denoted with 0 to n-1. Let k = a number from 0 to n!-1. Let p denote the permutation we will build. p(0) is the element the permutation maps 0 to, 1 maps to p(1), et cetera. Initially, set p(i) = i for all i from 0 to n-1. Do for m ranging from n down to 2: Set q equal to the quotient when k is divided by m. Set r equal to the remainder when k is divided by m. Swap p(r) with p(m-1). Set k equal to q. Note that if you want to generate a random permutation, forget about using k above, omit the steps of setting q and k, and replace the step of setting r with: Set r to a random integer from 0 to m-1, inclusive. -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
berman@shire.cs.psu.edu (Piotr Berman) (04/14/90)
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