Вот решение, которое позволяет выбрать размер перестановки. Например, помимо возможности генерировать все перестановки из 10 элементов, он может генерировать перестановки пар из 10 элементов. Также он переставляет списки произвольных объектов, а не только целых чисел.
Это PHP, но есть также JavaScript и Haskell имплементация.
function nth_permutation($atoms, $index, $size) {
for ($i = 0; $i < $size; $i++) {
$item = $index % count($atoms);
$index = floor($index / count($atoms));
$result[] = $atoms[$item];
array_splice($atoms, $item, 1);
}
return $result;
}
Пример использования:
for ($i = 0; $i < 6; $i++) {
print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB
Как это работает?
За этим стоит очень интересная идея. Давайте возьмем список A, B, C, D. Мы можем построить перестановку, вытягивая из нее элементы, как из колоды карт. Изначально мы можем нарисовать один из четырех элементов. Затем один из трех оставшихся элементов и так далее, пока, наконец, у нас ничего не останется.
Вот одна из возможных последовательностей выборов. Начиная сверху мы идем по третьему пути, затем по первому, второму и, наконец, по первому. И это наша перестановка № 13.
Подумайте о том, как при данной последовательности выборов вы получите алгоритмически число тринадцать. Затем измените алгоритм, и вы сможете восстановить последовательность из целого числа.
Попробуем найти общую схему для упаковки последовательности выборов в целое число без избыточности и ее распаковки обратно.
Одна интересная схема называется десятичной системой счисления. «27» можно рассматривать как выбор пути № 2 из 10, а затем выбор пути № 7 из 10.
Но каждая цифра может кодировать варианты только из 10 альтернатив. Другие системы с фиксированным основанием, такие как двоичные и шестнадцатеричные, также могут кодировать только последовательности выбора из фиксированного числа альтернатив. Нам нужна система с переменным основанием, вроде единиц времени: «14:05:29» - это час 14 из 24, минута 5 из 60, секунда 29 из 60.
Что, если мы возьмем общие функции для преобразования числа в строку и для преобразования строки в число и введем их в заблуждение с использованием смешанных оснований? Вместо того, чтобы принимать один ось, например, parseInt ('beef', 16) и (48879) .toString (16) , они будут принимать одно основание для каждой цифры.
function pack(digits, radixes) {
var n = 0;
for (var i = 0; i < digits.length; i++) {
n = n * radixes[i] + digits[i];
}
return n;
}
function unpack(n, radixes) {
var digits = [];
for (var i = radixes.length - 1; i >= 0; i--) {
digits.unshift(n % radixes[i]);
n = Math.floor(n / radixes[i]);
}
return digits;
}
Это вообще работает?
// Decimal system
pack([4, 2], [10, 10]); // => 42
// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42
// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42
А теперь задом наперед:
unpack(42, [10, 10]); // => [4, 2]
unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]
Это так прекрасно. Теперь давайте применим эту параметрическую систему счисления к проблеме перестановок. Мы рассмотрим перестановки длины 2 A, B, C, D. Сколько их всего? Давайте посмотрим: сначала мы рисуем один из 4 предметов, затем один из оставшихся 3, это 4 * 3 = 12 способов нарисовать 2 предмета. Эти 12 способов могут быть упакованы в целые числа [0..11]. Итак, давайте представим, что мы уже упаковали их, и попробуем распаковать:
for (var i = 0; i < 12; i++) {
console.log(unpack(i, [4, 3]));
}
// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]
Эти числа представляют варианты, а не индексы в исходном массиве. [0, 0] не означает взятие A, A, это означает, что нужно взять элемент № 0 из A, B, C, D (это A), а затем пункт # 0 из оставшегося списка B, C, D (это B). И в результате перестановка будет A, B.
Другой пример: [3, 2] означает получение элемента № 3 из A, B, C, D (это D) и затем пункта № 2 из оставшегося списка A, B, C (это C). И в результате перестановка будет D, C.
Это отображение называется Lehmer code . Давайте сопоставим все эти коды Лемера с перестановками:
AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
Это именно то, что нам нужно. Но если вы посмотрите на функцию unpack, вы заметите, что она производит цифры справа налево (чтобы изменить действия pack). Выбор из 3 распаковывается перед выбором из 4. Это неудачно, потому что мы хотим выбрать из 4 элементов, прежде чем выбрать из 3. Не имея возможности сделать это, мы должны сначала вычислить код Лемера, накопить его во временный массив, а затем примените его к массиву элементов для вычисления фактической перестановки.
Но если мы не заботимся о лексикографическом порядке, мы можем притвориться, что мы хотим выбрать из 3 элементов, прежде чем выбрать из 4. Затем выбор из 4 выйдет из unpack первым. Другими словами, мы будем использовать unpack(n, [3, 4]) вместо unpack(n, [4, 3]). Этот трюк позволяет вычислить следующую цифру кода Лемера и немедленно применить ее к списку. И именно так работает nth_permutation().
Последнее, что я хочу упомянуть, это то, что unpack(i, [4, 3]) тесно связано с системой факторных чисел. Посмотрите на это первое дерево еще раз, если мы хотим перестановки длины 2 без дубликатов, мы можем просто пропустить каждый второй индекс перестановки. Это даст нам 12 перестановок длины 4, которые можно обрезать до длины 2.
for (var i = 0; i < 12; i++) {
var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system
console.log(lehmer.slice(0, 2));
}