python - Filtrar un conjunto para hacer coincidir las permutaciones de cadena

algorithm permutation

Question

Estoy tratando de usar itertools.permutations () para devolver todas las permutaciones de la cadena y devolver solo las que son miembros de un conjunto de palabras .

import itertools

def permutations_in_dict(string, words): 
    ''''''
    Parameters
    ----------
    string : {str}
    words : {set}

    Returns
    -------
    list : {list} of {str}    

    Example
    -------
    >>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
    [''act'', ''cat'']
    ''''''

Mi solución actual funciona bien en la terminal pero de alguna manera no pudo pasar el caso de prueba ...

return list(set([''''.join(p) for p in itertools.permutations(string)]) & words)

Cualquier ayuda será apreciada.

Answer 1

Categoría de problema

El problema que está resolviendo se describe mejor como pruebas para coincidencias de anagram .

Solución utilizando Sort

La solución tradicional es ordenar la cadena de destino, ordenar la cadena candidata y probar la igualdad.

>>> def permutations_in_dict(string, words):
        target = sorted(string)
        return sorted(word for word in words if sorted(word) == target)

>>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
[''act'', ''cat'']

Solución utilizando Multisets

Otro enfoque es utilizar collections.Counter() para realizar una prueba de igualdad de conjuntos multiset . Esto es algorítmicamente superior a la solución de clasificación ( O(n) frente a O(n log n) ), pero tiende a perder a menos que el tamaño de las cadenas sea grande (debido al costo de hash de todos los caracteres).

>>> def permutations_in_dict(string, words):
        target = Counter(string)
        return sorted(word for word in words if Counter(word) == target)

>>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
[''act'', ''cat'']

Solución usando un hash perfecto

Una firma de anagrama única o un hash perfecto se puede construir multiplicando los números primos correspondientes a cada carácter posible en una cadena.

La propiedad conmutativa de la multiplicación garantiza que el valor de hash será invariante para cualquier permutación de una sola cadena. La unicidad del valor de hash está garantizada por el teorema fundamental de la aritmética (también conocido como el teorema de factorización prima única).

>>> from operator import mul
>>> primes = [2, 3, 5, 7, 11]
>>> primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
>>> anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))
>>> def permutations_in_dict(string, words):
        target = anagram_hash(string)
        return sorted(word for word in words if anagram_hash(word) == target)

>>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
[''act'', ''cat'']

Solución utilizando permutaciones.

La búsqueda por permutaciones en la cadena de destino utilizando itertools.permutations() es razonable cuando la cadena es pequeña (la generación de permutaciones en una cadena de n longitud genera n candidatos factoriales).

La buena noticia es que cuando n es pequeño y la cantidad de palabras es grande, este enfoque se ejecuta muy rápido (porque la prueba de membresía establecida es O (1)):

>>> from itertools import permutations
>>> def permutations_in_dict(string, words):
        perms = set(map(''''.join, permutations(string)))
        return sorted(word for word in words if word in perms)

>>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
[''act'', ''cat'']

Como el OP supuso, el bucle de búsqueda de python puro puede acelerarse a velocidad c usando set.intersection() :

>>> def permutations_in_dict(string, words):
        perms = set(map(''''.join, permutations(string)))
        return sorted(words & perms)

>>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
[''act'', ''cat'']

Mejor solución

La mejor solución depende de la longitud de la cadena y la longitud de las palabras . Los tiempos mostrarán cuál es el mejor para un problema particular.

Aquí hay algunos tiempos comparativos para los distintos enfoques que utilizan dos tamaños de cadena diferentes:

Timings with string_size=5 and words_size=1000000
-------------------------------------------------
0.01406    match_sort
0.06827    match_multiset
0.02167    match_perfect_hash
0.00224    match_permutations
0.00013    match_permutations_set

Timings with string_size=20 and words_size=1000000
--------------------------------------------------
2.19771    match_sort
8.38644    match_multiset
4.22723    match_perfect_hash
<takes "forever"> match_permutations
<takes "forever"> match_permutations_set

Los resultados indican que para cadenas pequeñas, el enfoque más rápido busca permutaciones en la cadena de destino utilizando set-intersection.

Para cadenas más grandes, el enfoque más rápido es la solución tradicional de clasificación y comparación.

Espero que este pequeño estudio algorítmico sea tan interesante como el que tengo. Las comidas para llevar son:

• Conjuntos, itertools y colecciones hacen un corto trabajo de problemas como este.
• Los tiempos de ejecución de Big-oh son importantes (n-factorial se desintegra para n grande).
• La sobrecarga constante es importante (la clasificación supera las multisets debido a la sobrecarga de hash).
• Las matemáticas discretas son un tesoro de ideas.
• Es difícil saber qué es lo mejor hasta que realice un análisis y ejecute los tiempos :-)

Configuración de tiempo

FWIW, aquí hay una configuración de prueba que usé para ejecutar los tiempos comparativos:

from collections import Counter
from itertools import permutations
from string import letters
from random import choice
from operator import mul
from time import time

def match_sort(string, words):
    target = sorted(string)
    return sorted(word for word in words if sorted(word) == target)

def match_multiset(string, words):
    target = Counter(string)
    return sorted(word for word in words if Counter(word) == target)

primes = [2, 3, 5, 7, 11]
primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))

def match_perfect_hash(string, words):
    target = anagram_hash(string)
    return sorted(word for word in words if anagram_hash(word) == target)

def match_permutations(string, words):
    perms = set(map(''''.join, permutations(string)))
    return sorted(word for word in words if word in perms)

def match_permutations_set(string, words):
    perms = set(map(''''.join, permutations(string)))
    return sorted(words & perms)

string_size = 5
words_size = 1000000

population = letters[: string_size+2]
words = set()
for i in range(words_size):
    word = ''''.join([choice(population) for i in range(string_size)])
    words.add(word)
string = word                # Arbitrarily search use the last word as the target

print ''Timings with string_size=%d and words_size=%d'' % (string_size, words_size)
for func in (match_sort, match_multiset, match_perfect_hash, match_permutations, match_permutations_set):
    start = time()
    func(string, words)
    end = time()
    print ''%-10.5f %s'' % (end - start, func.__name__)

Answer 2

¿Por qué molestarse con las permutaciones? Este es un problema mucho más simple si miras las palabras como diccionarios de letras. Estoy seguro de que hay una comprensión para hacerlo mejor que esto, pero:

    letters = dict()
    for i in word:
      letters[i] = letters.get(i, 0) + 1

haga esto para la palabra y luego para cada palabra en el conjunto, asegúrese de que el valor de cada tecla sea mayor o igual al valor de la palabra clave. Si lo es, agrégalo a tu salida.

Bonificación adicional: esto debería ser fácil de paralelizar si su lista de palabras es extremadamente larga.

Answer 3

Aparentemente, se espera que la salida se ordene alfabéticamente, por lo que esto debería hacer:

return sorted(set(''''.join(p) for p in itertools.permutations(string)) & words)

Answer 4

Prueba esta solución

list(map("".join, itertools.permutations(''act'')))
[''act'', ''atc'', ''cat'', ''cta'', ''tac'', ''tca'']

Podemos llamarlo listaA

listA = list(map("".join, itertools.permutations(''act'')))

Tu lista es listb

listB = [''cat'', ''rat'', ''dog'', ''act'']

Luego usa set intersection

list(set(listA) & set(listB))
[''cat'', ''act'']

Answer 5

Simplemente puede usar collections.Counter() para comparar las words con la string sin crear todas las permutations (esto explota con la longitud de la cadena):

from collections import Counter

def permutations_in_dict(string, words):
    c = Counter(string)
    return [w for w in words if c == Counter(w)]

>>> permutations_in_dict(''act'', {''cat'', ''rat'', ''dog'', ''act''})
[''cat'', ''act'']

Nota: los set s no están ordenados, por lo que si necesita un orden específico, es posible que deba ordenar el resultado, p. Ej return sorted(...)

Answer 6

Solo combina conjuntos de letras

set_string = set(string)    
return [w for w in words if set(w) == set_string]

Aquí están los tiempos de la respuesta superior (Python 3.6)

0.06000    match_multiset
0.02201    match_perfect_hash
0.00900    match_sort
0.00600    comprehension  <-- This answer
0.00098    match_permutations
0.00000    match_permutations_set