Mam około 20 krótkich strun, które chcę błagać. Chcę tylko permutacje, które mają len == 8.

Chciałbym uniknąć obliczania ewentualnej permutacji, jak widać poniżej:

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)

Ale to jest zbyt wolne? Jak mogę zmniejszyć liczbę obliczeń? (Nie wydawać przetwarzania i pamięci RAM).

1
larissa 2 sierpień 2020, 07:02

1 odpowiedź

Najlepsza odpowiedź

Pierwsza, oczywista rzecz do zrobienia jest filtrować dowolne struny o długości> 8:

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

Następnie możesz użyć drugiego argumentu itertools.permutations, aby ustawić liczbę żądanych przedmiotów. Jeśli nie masz pustych strun na swojej liście, nigdy nie będziesz potrzebował więcej niż 8 przedmiotów, więc możemy użyć 8 jako drugiego argumentu:

p = itertools.permutations(newList, 8)

Jednakże, jeśli którykolwiek z twoich strun jest Jednym ze sposobów na rozwiązanie tego jest iterowanie przez różne długości:

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

Jednak tutaj kończysz ogromną ilością permutacji do filtrowania: p (20, 8) + p (20, 7) + ... p (20, 1) = mniej więcej 5,5 mld, co jest niepraktyczne do pracy.

Inny kierunek

Zamiast korzystać z permutacji, użyjmy kombinacji, których istnieje znacznie mniej ("tylko" 263 949). Przypomnijmy, że w kombinacjach kolejność kombinowanych elementów nie ma znaczenia, podczas gdy w perkulacjach. W ten sposób możemy użyć mniejszego zestawu kombinacji do filtrowania długości 8, które chcemy:

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

Używanie () zamiast [] spowoduje, że ten generator niż lista, aby opóźnić ocenę, dopóki nie będziemy tego potrzebować. A teraz jesteśmy blisko!

Możemy uzyskać nasz końcowy wynik, podejmując permutacji elementów w cList:

result = [''.join(perm) for combo in cList 
    for perm in itertools.permutations(combo)]
3
jdaz 2 sierpień 2020, 08:14