Как работает этот алгоритм генерации лёссографских ордеров?

Question

от Wikipedia:

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

для каждого число К, причем 0 ≤ K < п !, следующего алгоритм генерирует соответствующий лексикографического перестановки исходной последовательности 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 
... 

Это означает, что Вранг-Вранг с помощью «переменных базового числа».

Теперь вы можете увидеть, как мы вычисляем цифру в месте в этой системе. Чтобы найти самое правильное, нам не нужно сначала делить, и мы находим остаток по модулю 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 начинается как (п-1)!

for j= 1 to n- 1 { 

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

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

Здесь мы разделим k на factorial (который равен (п-J)!) И выбросить остаток, то мы берем оставшиеся, когда мы разделим результат на (п + 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; 

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

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

Я надеюсь, что это поможет!

Answer 2

Придумайте многомерного массива, всех перестановок п элементов, с размерами:

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

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

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

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

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

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

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

Answer 3

Скажите, что u имеет начальную последовательность как [] = {1,2,3,4,5,6} n = 6; и вы хотите генерировать kth perm. С 1 на месте I, вы можете сгенерировать 5! (т. е. (n-1)!) перм с остальными местами.

1 ,....... 

Затем u xchange 1 и 2 и снова u может снова сгенерировать 5! перманент.

2 ,....... 

Итак, идея дана k, нам нужно найти степень k. Я имею в виду: say k is 225, how many 5! k имеет: 245/5! = 2 Итак, если k = 245, в перестановке, которую я хочу сгенерировать, первое место, безусловно, 3 (т. Е. [2]) (bcoz после перехода 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.) 

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