Как можно написать функцию (на Python), которая:
Если мы возьмем все перестановки для A, B и C: ABC, ACB, BAC, BCA, CAB, CBA
Функция берет индекс и возвращает перестановку для этого индекса.
Например. F("ABC", 4) вернет "BCA"
Он должен выполняться за разумное время для очень больших наборов перестановок.
Вы можете анализировать/фильтровать результаты itertools.permutations(), потому что генераторы не могут быть проиндексированы напрямую. Такая функция сделает это:
from itertools import permutations
def nth_permutation(items, n):
i = 0
perms = permutations(items)
try:
next_perm = next(perms)
while i < n:
next_perm = next(perms)
i += 1
except StopIteration:
# implement error behavior here, if n > number of permutations.
# For now we just return the default value, None
# you might instead try throwing an IndexError
return None
return next_perm
(обратите внимание, что перестановка с индексом 4 является "CAB" - "BCA" является индексом 3)
«Вам нужно будет проанализировать/отфильтровать результаты itertools.permutations()» — зачем так говорить? Довольно просто найти перестановку # 345 678 911 алфавита, фактически не создавая более одной перестановки.
Вам не нужно генерировать все перестановки до n-й; существует алгоритм для генерации n-й перестановки напрямую с использованием факториалов, которые можно найти в связанном дубликате.
Должен ли он работать в разумные сроки и для очень больших индексов?
Здравствуйте и добро пожаловать в coderhelper! Не могли бы вы поделиться тем, что вы пробовали до сих пор?
Каков порядок перестановок? Всегда ли оно лексикографично?
См.
itertools.permutationsв качестве отправной точки, но, вероятно, не для "очень больших наборов перестановок".В книге Стэнтона и Уайта «Конструктивная комбинаторика» содержится много таких алгоритмов. Он дает псевдокод, похожий на Pascal, который достаточно легко перевести на Python. Как общий ресурс для всех таких вопросов, я настоятельно рекомендую его.