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?

This problem is called the next permutation and it's answered here http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string — pkacprzak, Jul 19 '13 at 22:34

Kek · Accepted Answer · 2013-07-19T09:30:06.703

0

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

edited Jul 19 '13 at 09:30

answered Jul 19 '13 at 09:21

Kek

3,145
2
20
26

Sorry, I think your answer went over my head there. Are you checking if the letter on the right of the current letter is of a larger value? – entropy Jul 19 '13 at 09:24
No : you take n-1 => d. Next d, you have nothing, so you go back to n-2 => b. next b, you have c. so your word begins with ac. then, b and d remain, you simply order them : acbd. – Kek Jul 19 '13 at 09:28

score 0 · Answer 2 · answered Jul 19 '13 at 09:33

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;
        }
    }

}

How do lexicographical permutations work algorithmically?

2 Answers2