Как ограничить количество перестановок

Question

У меня есть около 20 коротких строк, которые я хочу переставить. Мне нужны только перестановки, которые имеют len == 8.

Я бы хотел избежать вычисления каждой возможной перестановки, как показано ниже:

import itertools
p = itertools.permutations([s1, s2, s3, s4, s5, s6,...])
for i in p:
    s = ''.join(j for j in i)
    if len(s)==8:
        print(s)

Но это слишком медленно, правда ? Как уменьшить количество вычислений? (чтобы не тратить обработку и оперативную память).

Answer 1

Первое, что необходимо сделать, это отфильтровать любые строки длиной> 8:

newList = [i for i in [s1, s2, s3, s4, s5, s6, ...] if len(i) <= 8]

Затем вы можете использовать второй аргумент itertools.permutations, чтобы установить количество элементов, которое вы хотите. Если в вашем списке нет пустых строк, вам никогда не понадобится более 8 элементов, поэтому мы можем использовать 8 в качестве второго аргумента:

p = itertools.permutations(newList, 8)

Однако, если какая-либо из ваших строк длиннее , чем один символ, это не даст вам того, что вы хотите, поскольку вернет только перестановки ровно 8 элементов. Один из способов решить эту проблему - перебрать разные длины:

pList = [itertools.permutations(newList, length) for length in range(1, 9)]

Но здесь вы получаете огромное количество перестановок для фильтрации: P (20, 8) + P (20, 7) + ... P (20, 1) = примерно 5,5 миллиарда , что непрактично для работы.

Другое направление

Вместо использования перестановок давайте использовать комбинации, которых намного меньше («всего» * ​​1019 * 263,949 ). Напомним, что в комбинациях порядок объединенных элементов не имеет значения, а в перестановках имеет значение. Таким образом, мы можем использовать меньший набор комбинаций для фильтрации по длине 8, которая нам нужна:

cList = (combo for length in range(1, 9) 
    for combo in itertools.combinations(newList, length) 
    if len(''.join(combo)) == 8)

Использование () вместо [] сделает его генератором, а не списком, чтобы отложить оценку пока оно нам действительно не понадобится. И теперь мы близки!

Мы можем получить наш окончательный результат, взяв перестановки элементов в cList:

result = [''.join(perm) for combo in cList 
    for perm in itertools.permutations(combo)]