Вычисление n-й 6-символьной перестановки алфавита

В течение нескольких дней я занимался поиском решения этой проблемы. Я был бы рад заплатить кому-то за консультацию, чтобы решить это, если потребуется.

В настоящее время я использую Python itertools для генерации 6 символьных перестановок из 32-символьного алфавита. С помощью следующей команды:

gen = itertools.permutations('ABCDEFGHJKLMNPQRSTUVWXYZ23456789',6) 

Из документации эта функция создает «кортежи r-длины, все возможные порядки, не повторяющиеся элементы».

Вы можете использовать библиотеку для захвата фрагмента полученных перестановок с помощью следующей команды (в этом примере захватываются первые 10 перестановок, 0-10:

 gen2 = itertools.islice(gen,0,10) 

При повторении результата gen2 я получаю именно то, что хочу:

 ('A', 'B', 'C', 'D', 'E', 'F') ('A', 'B', 'C', 'D', 'E', 'G') ('A', 'B', 'C', 'D', 'E', 'H') ('A', 'B', 'C', 'D', 'E', 'J') ('A', 'B', 'C', 'D', 'E', 'K') ('A', 'B', 'C', 'D', 'E', 'L') ('A', 'B', 'C', 'D', 'E', 'M') ('A', 'B', 'C', 'D', 'E', 'N') ('A', 'B', 'C', 'D', 'E', 'P') ('A', 'B', 'C', 'D', 'E', 'Q') 

Это здорово, но мое реальное желание – выбрать любую произвольную перестановку и захватить ее из списка перестановок (без сохранения всех возможных значений перестановок). Если мои вычисления верны, то при генерации 6 последовательностей символов указанного выше алфавита имеется 652 458 240 возможных комбинаций. Поэтому я хотел бы сделать что-то вроде захвата 10 353 345-й перестановки. Проблема в том, что если вы используете функцию islice выше, чтобы захватить эту перестановку, она должна выполнить итерацию по всему набору перестановок до 10 353 345-го элемента, прежде чем вернуть его вам. Как вы можете себе представить, это очень неэффективно и требуется много времени, чтобы вернуться.

Мой вопрос: какой алгоритм для достижения желаемого вычисления? Я провел довольно много исследований по факториальной декомпозиции и базовым преобразованиям, но не смог найти ничего, объясняющего, как достичь чего-то близкого к тому, что я хочу, или алгоритма, который я могу изменить для достижения этого результата.

Любая помощь будет принята с благодарностью!

2 Solutions collect form web for “Вычисление n-й 6-символьной перестановки алфавита”

То, что вы ищете, называется unrank в комбинаторном алгоритме. Рассмотрим список элементов множества S в фиксированном порядке, unrank_S(i) возвращает i элемент списка без вычисления списка. Таким образом, ваш S – это Perm(n, k) : список всех k преобразований набора размеров n . Как вы знаете, размер этого набора равен n!/k! , Один из способов сделать это – использовать факторные числа

Вот алгоритм unrank в python:

 def factorial(n): if n == 0: return 1 return n*factorial(n-1) def unrank(S, k, i): n = len(S) nb = factorial(n) // factorial(nk) if i >= nb: raise IndexError res = [] while k > 0: nb = nb // n pos = i // nb # the factoradic digits i = i % nb # the remaining digits res.append(S[pos]) del S[pos] k = k-1 n = n-1 return res 

затем

 [unrank(range(5), 2, i) for i in range(20)] [[0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3]] 

а также

 unrank(list('ABCDEFGHJKLMNPQRSTUVWXYZ23456789'),6, 128347238)\ ['G', 'L', 'E', 'H', 'T', 'R'] 

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

У меня нет много времени, чтобы дать вам полное решение, но следующая идея может предоставить некоторую линию для размышлений.

Вам нужно найти N- ю перестановку с 6 символами за раз.
Позволяет исправить персонаж первого места. Затем остается 25 других символов.
Общее количество перестановок из оставшихся символов равно P = 25 C 5 * 5! ,

Таким образом, с A в качестве первого символа вы можете иметь P- перестановки. Если P меньше N , то A не может быть на первом месте.

Теперь держите B на первом месте и общее количество перестановок до B на первом месте – 2 * P.

Предположим, что вы держите K- й символ на первом месте, так что общее количество перестановок до K- го символа составляет K * P , причем K * P меньше N , и после сохранения K + 1- го символа (K + 1) * P превышает N. Таким образом, ваша требуемая строка должна иметь K + 1- й символ на первом месте.

Поэтому вам нужно найти оставшиеся перестановки NK * P. с остальными 25 символами и 5 местами. Таким образом, одна и та же проблема сокращается до 1 символа меньше, на 1 место меньше и меньше количества перестановок.
Поэтому решайте аналогичным образом для всех мест.

  • Попытка группировать ценности?
  • Python реализация интервала оценки Wilson?
  • Эффективный расчет бета-счета Pandas Pandas на многих фреймах данных
  • Упражнение 6 главы 12 (кортежи) Think Python Аллена Дней
  • Панды: наиболее эффективный способ применения комплексной функции по всему кадру данных
  • Найти число вхождений подпоследовательности в строку
  • Что вызывает негативное уклонение в моей симуляции супер-выборки?
  • Быстрый способ найти нулевой ответ
  • Python - лучший язык программирования в мире.