Представьте, что у вас есть целое число 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, потому что есть три возможных значения для этого столбца. Продолжая влево, для 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 действительно всегда (n-j)!
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;
Далее, (н-ж)! деленное на (n-j) дает (n-j-1)!
Если вы подумаете об этом, вы должны увидеть, что это означает, что когда мы вернемся к вершине цикла и увеличим j на единицу, factorial снова будет равно (n-j)!
factorial:= factorial/ (n- j);
}
return s;
}
Надеюсь, это немного поможет!