🚀 go-pugleaf

Just some thoughts......

The original problem asked for ways to generate permutations
of N numbers given an "index" number in the range 0 ... N!-1

The algorithms I have found (and the ones proposed by others)
more or less consist of two steps. If somebody has another alternative,
I'll be glad to hear it!

Step 1:
    Given the "index", construct a set of N integers A[i], (i=0...n-1)
    so that:
	0<= A[0] < N
	0<= A[1] < N-1
	   ....
	0<= A[i] < N-i
	   ....
	0<= A[n-2] < 2
	0<= A[n-1] < 1 ==> A[n-1] = 0
    An algorithm that generates these numbers is:
	for i=0 to N-1 {
	    A[i] = index % (N-i)
	    index = index / (N-i)
	}
    where '%' is the modulo operator, and '/' the *integer* division
    (i.e. 3/2 = 1)
    Obviously each index in the range  [0 ... N!-1] gives a unique
    set of such numbers and vice versa.

Step 2:
    Use these numbers to choose elements for the permutation.
    Use A[0] to choose the first element of your permutation,
    then use A[1] to choose another element (out of the remaining
    N-1 elements) etc.

In order for the algorithm to be correct, each index number
must give a permutation and two different numbers must give
different permutations (i.e. there are no permutations
left out). The first part (i.e. always being able to produce a
permutation from a given index) is easy (afterall, that's what
the algorithm does!). To prove the second part, all we have to
do is prove that given a permutation, we can "reconstruct" the
corresponding index number (by following the steps of the
algorithm backwards).

For example, the most obvious (but inefficient) choice for Step 2
is:
    Construct a list with all your elements
    for i=0 to N-1 {
	take the A[i]-th element of the list,
	use it as the i-th element of your permutation
	and remove if from the list
    }

    (NOTE: the first element of the list is element # 0)

The only problem with this, is that finding an element of a list
and removing is an expensive operation. If the list is implemented as
an array, when removing an element we have to shift the remaining
elements one position down. If we use a linked list, then the removal
is easy (just updating pointers) but finding the n-th element of the
list is expensive again (we have to count all the previous ones first)
In both cases, the above algorithm will require O(n^2) time.

A faster version was proposed by David Karr (I think, the article has
expired and I didn't save it, apologies to the original poster if 
I am wrong).

	for i=0 to N-1 {
	    take the A[i]-th element of the list
	    and use it as the i-th element of the permutation
	    and replace it with the last element of the list
	}
    
For example, for N=3, index=4 we have:
    A[1] = 0, A[1] = 1, A[2] = 0
If the list of elements is  "A B C" then first we take
element #1 i.e. "B" (remember, "A" is element #0).
Then replace it with the last element "C", so now the list becomes
"A C". Then we take the A[1]-th element, i.e. element #1, i.e "C".
Eventually we end up with the permutation "B C A"

To prove that this algorithm is correct, we must be able to
"reconstruct" the index given a permutation. You might have to try a
few examples yourself, but (I think!) this is always possible.
In the previous example, we have the permutation BCA (starting from
ABC).  The first element is "B", i.e. element #1, so A[0] = 1.
So, we know that during the first iteration of the algorithm
we removed B out of ABC and replace it with the last element C,
so just before the second iteration the list was "AC".
The second element of the permutation is "C", i.e. element #1, so
A[1] = 1, and so forth....

Obviously this algorithm take O(n) time and O(n) space.


dougm@titan.cs.rice.edu (Doug Moore) writes:

>Now that the problem of computing a 1-1 mapping from the integers 0 <=
>i < n! to permutations of n elements has been solved, can anyone
>suggest a way to compute a function f(i,j), 0 <= i < n!, 0 <= j < n,
>such that f(i,j) is the jth component of the ith permutation IN
>CONSTANT SPACE?  Personally, I can't.  Maybe it's impossible.
>
>An application?  Suppose you wanted to implement a truly uniform
>open-addressed hashing scheme.  The algorithms proposed so far will
>generate a permutation (probe sequence) from a key, but require linear
>additional space to do it.  That would not be acceptible for a large
>hash table.  Any ideas?
>
>Doug Moore
>(dougm@cs.rice.edu)

I am not sure that I understood your question, but O(n)
space is not bad at all, unless you are thinking of *really* large
values of N (say tens or hundreds of thousands). But in this case we
are doomed anyway, because the index number will need much more space
to be represented!!!!. Some hasty calculations (so take them with a
pinch of salt - or maybe a tablespoon :-) indicate that we need O(n^2)
space to represent "n!". 

However if you are only going to use small values of index (i.e. only
use the "first" few permutations) then there might be a way,
but you must also choose an algorithm that (for these index values)
will also generate permutations that are quite "different" (they don't
start with the same element, etc.)

Spyros Potamianos
potamian@hpl.hp.com