How do lexicographical permutations work algorithmically?

Question

or example, if you are given "abcd", the lexicographical permutations would be:

abcd
abdc 
acbd
acdb 
adbc 
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

I understand intuitively how it is meant to be sorted and if you gave me any set of letters or numbers I could work it out for how they should be sorted, but not mathematically of how you would get from the one step to the next. For example: What is the mathematical process that takes you from abdc to acbd?

Answer 1

Well, one option could be :

to go from one step to the next,

• Let p = n-1
• you take (p)th letter abdc => d.
  • you take next letter according to your order.
    • if it exists, then you write it, then end your word with remaining letters ordered
    • else, p = p - 1 and you go back to previous step.

Not sure it is the best way to do. Why wanting to go from one step to next ? why not writing all words, begining by writing (n-1)! words begining by first letter, then (n -1)! by second...

a
a
...
a
b
b
...
b

for each one of these words : continue (n-2)! with second letter and (n-2)! with third letter :

ab
ab
...
ab
ac
ac
....
ac
....
ba
ba
...
bc
bc
....

and so on

Answer 2

If English is my native language, I could explain every aspect of this problem to you. Now just give my code(it explain itself) for permutation of integer:

const int maxn = 2000;
int x[maxn];
void next_permutation(int n)
{
    int i;
    int min_suffix = INT_MAX;
    int min_index = -1;
    for(i=n-1; i>0; --i){
        if(x[i] < x[i+1])break;
    }
    if(i==0){
        for(int i=1; i<=n; ++i){
            x[i] = i;
        }
        return;
    }

    for(int j=i+1; j<=n; ++j){
        if(x[j]>x[i] && x[j]<min_suffix){
            min_suffix = x[j];
            min_index = j;
        }
    }
    //swap x[i], x[min_index];
    {
        int tmp = x[i];
        x[i] = x[min_index];
        x[min_index] = tmp;
    }

    //insert_sort x[i+1...n]
    {
        for(int j=i+2; j<=n; ++j){
            int k;
            for(k=j-1; k>=i+1; --k){
                if(x[j]>x[k])break;
            }

            int tmp = x[j];
            for(int l=j-1; l>k; --l){
                x[l+1] = x[l];
            }
            x[k+1] = tmp;
        }
    }

}