Как алгоритмически работают лексикографические перестановки?

Ну, один из вариантов может быть:

переходить от одного шага к другому,

• Пусть р = п-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
    • иначе p = p - 1, и вы возвращаетесь к предыдущему шагу.

Не уверен, что это лучший способ сделать. Почему хочется переходить от одного шага к другому? почему бы не написать все слова, начиная с написания (n-1)! слова, начинающиеся с первой буквы, затем (n -1)! на секунду...

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

для каждого из этих слов: продолжить (n-2)! со второй буквой и (n-2)! с третьей буквы:

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

и так далее

Если бы английский был моим родным языком, я мог бы объяснить вам каждый аспект этой проблемы. Теперь просто дайте мой код (он сам себя объясняет) для перестановки целого числа:

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

}