Tengo alrededor de 20 cadenas cortas que quiero permutar. Solo quiero permutaciones que tengan len == 8.

Me gustaría evitar calcular cada permutación posible, como se ve a continuación:

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)

Pero eso es demasiado lento, ¿verdad? ¿Cómo puedo reducir el número de cálculos? (para no gastar procesamiento y RAM).

1
larissa 2 ago. 2020 a las 07:02

1 respuesta

La mejor respuesta

La primera cosa obvia que debe hacer es filtrar cualquier cadena con una longitud> 8:

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

Luego, puede usar el segundo argumento de itertools.permutations para establecer la cantidad de elementos que desea. Si no tiene cadenas vacías en su lista, nunca necesitará más de 8 elementos, por lo que podemos usar 8 como segundo argumento:

p = itertools.permutations(newList, 8)

Sin embargo, si alguna de sus cadenas es más larga que un carácter, esto no le dará lo que desea, ya que solo devolverá permutaciones de exactamente 8 elementos. Una forma de resolver esto es iterar a través de las distintas longitudes:

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

Sin embargo, aquí terminas con una enorme cantidad de permutaciones para filtrar: P (20, 8) + P (20, 7) + ... P (20, 1) = aproximadamente 5.5 billones, con lo cual no es práctico trabajar.

Una direccion diferente

En lugar de usar permutaciones, usemos combinaciones, de las cuales hay muchas menos ("solo" 263,949). Recuerde que en las combinaciones, el orden de los elementos combinados no importa, mientras que en las permutaciones sí. Por lo tanto, podemos usar el conjunto más pequeño de combinaciones para filtrar por la longitud 8 que queremos:

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

El uso de () en lugar de [] hará que este sea un generador en lugar de una lista, para retrasar la evaluación hasta que realmente lo necesitemos. ¡Y ahora estamos cerca!

Podemos obtener nuestro resultado final tomando las permutaciones de los elementos en cList:

result = [''.join(perm) for combo in cList 
    for perm in itertools.permutations(combo)]
3
jdaz 2 ago. 2020 a las 08:14