Поиск n-й перестановки без вычисления других

Как заявил Рикки Бобби, при рассмотрении лексикографического порядка перестановок вы должны использовать факториальное разложение в ваших интересах.

С практической точки зрения, вот как я это вижу:

• Выполните своеобразное эвклидово деление, за исключением того, что вы делаете это с факториальными числами, начиная с (n-1)! , (n-2)! , и так далее.
• Храните факторы в массиве. i фактор должен быть числом от 0 до ni-1 включительно, где i идет от 0 до n-1 .
• Этот массив является вашей перестановкой. Проблема в том, что каждый фактор не заботится о предыдущих значениях, поэтому вам нужно их настроить. Более конкретно, вам нужно увеличивать каждое значение столько раз, сколько есть более ранних или более низких значений.

Следующий код C должен дать вам представление о том, как это работает ( n – количество записей, а i – индекс перестановки):

 /** * @param n The number of entries * @param i The index of the permutation */ void ithPermutation(const int n, int i) { int j, k = 0; int *fact = (int *)calloc(n, sizeof(int)); int *perm = (int *)calloc(n, sizeof(int)); // compute factorial numbers fact[k] = 1; while (++k < n) fact[k] = fact[k - 1] * k; // compute factorial code for (k = 0; k < n; ++k) { perm[k] = i / fact[n - 1 - k]; i = i % fact[n - 1 - k]; } // readjust values to obtain the permutation // start from the end and check if preceding values are lower for (k = n - 1; k > 0; --k) for (j = k - 1; j >= 0; --j) if (perm[j] <= perm[k]) perm[k]++; // print permutation for (k = 0; k < n; ++k) printf("%d ", perm[k]); printf("\n"); free(fact); free(perm); } 

Например, ithPermutation(10, 3628799) печатает, как и ожидалось, последнюю перестановку из десяти элементов:

 9 8 7 6 5 4 3 2 1 0 

Вот решение, позволяющее выбрать размер перестановки. Например, помимо возможности генерации всех перестановок из 10 элементов, он может генерировать перестановки пар среди 10 элементов. Также он переставляет списки произвольных объектов, а не только целые числа.

Это PHP, но есть также JavaScript и Haskell impementation.

 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 ('говядина', 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 с перестановками:

 AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC 

Это именно то, что нам нужно. Но если вы посмотрите на функцию unpack вы заметите, что она производит цифры справа налево (чтобы отменить действия pack ). Выбор из 3 распаковывается перед выбором из 4. Это несчастливо, потому что мы хотим выбрать из 4 элементов, прежде чем выбирать из 3. Не имея возможности сделать это, мы сначала вычислим код Lehmer, аккумулируем его во временный массив, а затем примените его к массиву элементов для вычисления фактической перестановки.

Но если нас не интересует лексикографический порядок, мы можем притворяться, что хотим выбрать из 3 элементов, прежде чем выбирать из 4. Тогда выбор из 4 выйдет из unpack первую очередь. Другими словами, вместо unpack(n, [4, 3]) мы будем использовать unpack(n, [3, 4]) unpack(n, [4, 3]) . Этот трюк позволяет вычислить следующую цифру кода Lehmer и немедленно применить ее к списку. И именно так работает 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)); } 

Это зависит от того, как вы «сортируете» свои перестановки (например, лексикографический порядок).

Один из способов сделать это – система факториалов , это дает вам биекцию между [0, n!] И всеми перестановками.

Тогда для любого числа i из [0, n!] Вы можете вычислить i-ю перестановку, не вычисляя остальные.

Это факториальное письмо основано на том, что любое число между [0 и n!] Может быть записано как:

 SUM( ai.(i!) for i in range [0,n-1]) where ai <i 

(это очень похоже на декомпозицию базы)

для получения дополнительной информации об этом разложении, посмотрите на эту тему: https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

Надеюсь, поможет

Как указано в этой статье в Википедии, этот подход эквивалентен вычислению кода лемера :

Очевидным способом генерации перестановок n является генерация значений для кода Лемера (возможно, с использованием системного представления числовых чисел целых чисел до n!) И преобразования их в соответствующие перестановки. Однако последний шаг, хотя и простой, трудно реализовать эффективно, поскольку он требует n операций, каждый из которых выбирается из последовательности и удаляется из него, в произвольной позиции; из очевидных представлений последовательности в виде массива или связанного списка, оба требуют (по разным причинам) порядка n2 / 4 операций для выполнения преобразования. Поскольку n может быть довольно небольшим (особенно если требуется генерация всех перестановок), это не слишком большая проблема, но оказывается, что и для случайного, и для систематического генерации существуют простые альтернативы, которые значительно улучшаются. По этой причине представляется бесполезным, хотя, безусловно, возможным использование специальной структуры данных, которая позволила бы выполнить преобразование из кода Лехмера в перестановку в O (n log n) времени.

Таким образом, лучшее, что вы можете сделать для набора элементов n, – это O (n ln (n)) с адаптированной структурой данных.

Вот алгоритм преобразования между перестановками и рангами в линейном времени. Однако ранжирование, которое он использует, не является лексикографическим. Это странно, но непротиворечиво. Я собираюсь дать две функции, которые преобразуются из ранга в подстановку, и одну, которая делает обратную.

Во-первых, чтобы отказаться (перейти от ранга к перестановке)

 Initialize: n = length(permutation) r = desired rank p = identity permutation of n elements [0, 1, ..., n] unrank(n, r, p) if n > 0 then swap(p[n-1], p[r mod n]) unrank(n-1, floor(r/n), p) fi end 

Затем, чтобы оценить:

 Initialize: p = input permutation q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n) n = length(p) rank(n, p, q) if n=1 then return 0 fi s = p[n-1] swap(p[n-1], p[q[n-1]]) swap(q[s], q[n-1]) return s + n * rank(n-1, p, q) end 

Время работы обоих из них – O (n).

Есть хорошая, читаемая статья, объясняющая, почему это работает: ранжирование и разблокирование перестановок в линейном времени, by Myrvold & Ruskey, письма для обработки информации Том 79, выпуск 6, 30 сентября 2001 г., стр. 281-284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Вот краткое и очень быстрое (линейное по количеству элементов) решение в python, работающее для любого списка элементов (13 первых букв в примере ниже):

 from math import factorial def nthPerm(n,elems):#with n from 0 if(len(elems) == 1): return elems[0] sizeGroup = factorial(len(elems)-1) q,r = divmod(n,sizeGroup) v = elems[q] elems.remove(v) return v + ", " + ithPerm(r,elems) 

Примеры :

 letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m'] ithPerm(0,letters[:]) #--> a, b, c, d, e, f, g, h, i, j, k, l, m ithPerm(4,letters[:]) #--> a, b, c, d, e, f, g, h, i, j, m, k, l ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j 

Примечание. Я пишу letters[:] (копия letters ), а не буквы, потому что функция изменяет свой параметр elems (удаляет выбранный элемент)

Если вы сохраните все перестановки в памяти, например, в массиве, вы сможете вернуть их по одному за раз в O (1) раз.

Это означает, что вы должны хранить все перестановки, поэтому, если вычисление всех перестановок занимает слишком много времени или их хранение занимает непомерно большое пространство, это может быть не решение.

Мое предложение состояло бы в том, чтобы попробовать все равно, и вернуться, если он слишком большой / медленный – нет смысла искать «умное» решение, если наивный будет выполнять эту работу.