[pyar] Ejercicio (para entretenerse)

[Matías Bellone]

2012/1/13 fisa <fisadev en gmail.com>:
> El día 13 de enero de 2012 13:14, Lucio Torre <lucio.torre en gmail.com> escribió:
>> On Fri, Jan 13, 2012 at 11:44 AM, Sebastian Bassi
>> <sebastian.bassi en globant.com> wrote:
>>> De casualidad encontré una página que propone el siguiente problema, lo
>>> posteo porque se de varios que le gustan resolver estas cosas:
>>
>> Obviamente lo interesante aca es hacerlo en O(N), no O(N**2). Es
>> decir, no podes hacer una funcion que sea is_anagram(w1, w2) y hacer
>> todos contra todos.
>>
>> Lucio.
>
> Asumiendo que el .get de los diccionarios es O(1), esto sería O(N) con
> N = cantidad de palabras, no?
>
> palabras = 'abracadabra beards breads constant learner myopic
> relearn'.lower().split()
> abecedario = 'abcdefghijklmnopqrstuvwxyz'
>
> resultados = {}
>
> for p in palabras:
>    letras = {}
>    for l in p:
>        letras[l] = letras.get(l, 0) + 1
>
>    hash = ''.join(l + str(letras.get(l,0)) for l in abecedario)
>
>    resultados[hash] = resultados.get(hash, []) + [p,]
>
> # esto es para mostrar los resultados, no entra dentro del O del
> proceso para obtenerlos
> print '\n'.join(' '.join(r)
>                for r in resultados.values()
>                if len(r) > 1)
>

Algo parecido a lo de fisa pero - a mí parecer - más legible:


>>> from collections import defaultdict
>>> def anagram(words):
...     matches = defaultdict(lambda: list())
...     for word in words:
...             letters = list(word)
...             letters.sort()
...             hash = tuple(letters) # lista ordenada de todas las letras
...             matches[hash].append(word)
...     return [x for x in matches.values() if len(x) > 1] # solo las
palabras con "parejas"
...
>>> anagram(['breads', 'beards', 'abracadabra','constant', 'learner', 'myopic', 'relearn'])
[['breads', 'beards'], ['learner', 'relearn']]

Saludos,
Toote
-- 
Web: http://www.enespanol.com.ar