How does this "Lexographic order generation algorithm" work?

Question

from Wikipedia:

Lexicographical order generation

For every number k, with 0 ≤ k < n!, the following algorithm generates the corresponding lexicographical permutation of the initial sequence sj, j = 1, ..., n:

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

What is the logic behind this? How does it work??

Answer 1

Think of a multi-dimensional array, of all the permutations of n items, with dimensions:

p[n][n-1][n-2]...[1]

Any multi-dimensional array can be linearized into a 1d array of dimension:

a[n*(n-1)*(n-2)*...*1]

It's like a variable-base number; going in order of numeric value does give you lexicographic order on the digits.

The index you use to refer to a tuple x[n] = e.g. (i[n],i[n-1]...,i[0]) is sum_j i[j]*(j!)

So, the division/mod is recovering the next position from the tuple.

The value of the kth index in the tuple is the product of the dimensions to its right, which happens to be k!.

Answer 2

Imagine you have a whole number x and you want to know what digit is in the hundreds position. (E.g. if x=4723 you want the answer 7.) To calculate this, you first divide by 100, throwing away the fractional part. (In our example, this leaves 47.) Then find the remainder when you divide by 10.

Now suppose you want to find the value of the digit in the thousands position. To find that you'd first divide by 1000, throwing away the fractional part, then again find the remainder when you divide by 10.

In the regular decimal numbering system, each place holds one of 10 values. You can observe that in our digit-finding exercise we first divide by the number of possible combinations of values in places to the right of the one we care about (10 * 10 in the first example). Then we find the remainder when dividing by the number of possible values for the place we care about. Of course, all places have 10 possible values, so we just divide by 10.

Now, imagine a numbering system where each place holds a different number of values. Our right-most place can have two values, 0 or 1. The next place can have three values, 0, 1 or 2; and so on. In this system we count like this:

  0
  1
 10
 11
 20
 21
100
101
110
111
120
121
200
201
210
211
220
...

This is what wrang-wrang means by a "variable-base number".

Now, you can see how we calculate the digit in a place in this system. To find the right-most we don't need to divide first, and we find the remainder modulo 2, because there are 2 possible values for a digit in that column. To find the next column to the left, we first divide by the number of possible combinations for digits in the columns on the right: there's only one column with two possible digits, so we divide by 2. Then we take the remainder modulo 3, because there are three possible values for this column. Continuing left, for the 3rd column we divide by 6 (because the columns to the right have 3 and 2 possibilities each, multiplying to make 6) and then take the remainder modulo 4, because there are 4 possible values in this column.

Let's take a look at the function:

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial starts as (n-1)!

    for j= 1 to n- 1 {

Each time we get here, factorial is equal to (n-j)! This is obvious the first time round, since j=1 and we know we initialized factorial to (n-1)! We'll see later that factorial is indeed always (n-j)!

        tempj:= (k/ factorial) mod (n+ 1- j);

Here we divide k by factorial (which is equal to (n-j)!) and throw away the remainder, then we take the remained when we divide the result by (n+1-j). Wait a minute, all that babble I started with is beginning to sound familiar! We are just finding the value of the "digit" in the nth column from the left using our "variable-base number system"!

This next bit takes the sequence of elements between indices j and j + tempj and rotates it rightward - i.e. every element moves up one index, except the last one, which moves back to the start. It's important to realise that all the numbers on the right of position j are in order. We're effectively plucking one of them out and nudging the rest along to keep them in order. Which one we pluck out depends on tempj. When tempj is 0, we pick the smallest (and actually don't need to do any nudging), when tempj is equal to n-j, we pick the largest.

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

Next, (n-j)! divided by (n-j) gives (n-j-1)! If you think about it, you should see that this means that when we get back to the top of the loop and j has incremented by one, factorial will once again equal (n-j)!

        factorial:= factorial/ (n- j);
    }
    return s;
}

I hope that helps a bit!

Answer 3

Say u have initial sequence as a[] = { 1,2,3,4,5,6 }of n = 6; and u want to generate kth perm. With 1 on Ist place, u can generate 5! (i.e. (n-1)! ) perms with the remaining places.

1 ,.......

Then u xchange 1 and 2 and again u can again generate 5! perms.

2 ,.......

So the idea is given k, we need to find the extent of k. What I mean is: say k is 225, how many 5! does k have: 245/5! = 2 So if k = 245, in the permutation that I want to generate, the first place is definitely 3 (i.e. a[2]) (bcoz after going 2*5! = 240 , I will xchange 1 and 3), I will have

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

that's why in the algo, u do k/(n-1)! in the first iteration. And obtain remainder k = k mod (n-1)!. This is new value of k and u go recursively doing the same thing with (n-j)! on the remaining places.