Как работает этот «алгоритм генерации лексографического порядка»?

Question

от Википедия:

Генерация лексикографического порядка

Для каждого числа k, с 0 ≤ k <n!, Следующий алгоритм генерирует соответствующую лексикографическую перестановку начальной последовательности 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;
 }

Что логика за этим? Как это работает??

Answer 1

Представьте, что у вас есть целое число x и вы хотите знать, какая цифра стоит в позиции сотен.(Например.если x=4723, вам нужен ответ 7.) Чтобы вычислить это, вы сначала делите на 100, отбрасывая дробную часть.(В нашем примере остается 47.) Затем найдите остаток, разделив на 10.

Теперь предположим, что вы хотите найти значение цифры в позиции тысяч.Чтобы обнаружить, что сначала нужно разделить на 1000, отбросив дробную часть, а затем снова найти остаток, разделив на 10.

В обычной десятичной системе счисления каждое место содержит одно из 10 значений.Вы можете заметить, что в нашем упражнении по поиску цифр мы сначала делим на количество возможных комбинаций значений в местах справа от того, которое нас интересует (10 * 10 в первом примере).Затем находим остаток при делении на количество возможных значений интересующего нас места.Конечно, все мест имеют 10 возможных значений, поэтому мы просто делим на 10.

Сейчас, представьте себе систему нумерации, в которой каждое место содержит разное количество значений.Наше самое правое место может иметь два значения: 0 или 1.Следующее место может иметь три значения: 0, 1 или 2;и так далее.В этой системе мы считаем так:

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

Вот что Wrang-Wrang подразумевает под «числом с переменной базой».

Теперь вы можете увидеть, как мы вычисляем цифру в месте этой системы.Чтобы найти самое правое, нам не нужно сначала делить, а мы находим остаток по модулю 2, потому что для цифры в этом столбце есть 2 возможных значения.Чтобы найти следующий столбец слева, сначала разделим на количество возможных комбинаций цифр в столбцах справа:есть только один столбец с двумя возможными цифрами, поэтому мы делим на 2.Затем мы берем остаток по модулю 3, потому что для этого столбца есть три возможных значения.Продолжая двигаться влево, для третьего столбца мы делим на 6 (потому что столбцы справа имеют по 3 и 2 возможности каждый, умножая, чтобы получить 6), а затем берем остаток по модулю 4, потому что в этом столбце 4 возможных значения.

Давайте посмотрим на функцию:

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

factorial начинается как (n-1)!

    for j= 1 to n- 1 {

Каждый раз, когда мы приходим сюда, factorial равно (n-j)!Это очевидно с первого раза, поскольку j=1, и мы знаем, что инициализировали factorial до (n-1)!Мы увидим это позже factorial действительно всегда (nj)!

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

Здесь мы делим k к factorial (который равен (n-j)!) и отбрасываем остаток, затем берем остаток, когда делим результат на (n+1-j).Подождите, вся эта болтовня, с которой я начал, начинает звучать знакомо!Мы просто находим значение «цифры» в n-м столбце слева, используя нашу «систему счисления с переменной базой»!

Следующий бит принимает последовательность элементов между индексами. j и j + tempj и поворачивает его вправо - т.е.каждый элемент перемещается на один индекс вверх, кроме последнего, который возвращается в начало.Важно понимать, что все числа справа от позиции j стоят по порядку.Мы эффективно выдергиваем один из них и подталкиваем остальных, чтобы поддерживать их в порядке.Какой из них мы выдернем, зависит от tempj.Когда tempj равно 0, мы выбираем наименьшее значение (и фактически не нуждаемся в каких-либо подталкиваниях), когда tempj равно n-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;

Далее, (н-дж)!разделить на (nj) дает (nj-1)!Если вы подумаете об этом, то увидите, что это означает, что когда мы вернемся к началу цикла и j увеличился на единицу, factorial снова будет равно (n-j)!

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

Надеюсь, это немного поможет!

Answer 2

Представьте себе многомерный массив, состоящий из всех перестановок из n элементов, с размерами:

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

Любой многомерный массив можно линеаризовать в одномерный массив:

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

Это похоже на число с переменной базой;движение в порядке числовых значений дает вам лексикографический порядок цифр.

Индекс, который вы используете для ссылки на кортеж x[n] = например. (i[n],i[n-1]...,i[0]) является sum_j i[j]*(j!)

Итак, деление/мод восстанавливает следующую позицию из кортежа.

Значение k-го индекса в кортеже — это произведение измерений справа от него, которое равно k!.

Answer 3

Скажем, у вас есть начальная последовательность a[] = { 1,2,3,4,5,6 } of n = 6;и вы хотите создать k-е разрешение.Если 1 на первом месте, вы можете создать 5!(т.е.(n-1)!) завивка с оставшимися местами.

1 ,.......  

Затем вы меняете местами 1 и 2 и снова можете снова сгенерировать 5!завивка.

2 ,.......

Итак, если идея задана k, нам нужно найти степень k.Я имею в виду:скажем, к — 225, сколько 5!есть ли у k:245/5!= 2 Итак, если k = 245, в перестановке, которую я хочу генерировать, первое место определенно 3 (т.е.a[2]) (потому что после 2*5!= 240, я поменяю местами 1 и 3), у меня будет

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.)

вот почему в алгоритме вы делаете k/(n-1)!в первой итерации.И получим остаток k = k mod (n-1)!.Это новое значение k, и вы рекурсивно делаете то же самое с (n-j)!на остальных местах.