Módulo para combinatoria

[Jesus Cea]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Chema Cortes wrote:
>> Lo preguntaba porque estaba tratando de hacer un divertimento del tipo
>> "Cifras y letras" (para quien no lo conozca, es un programa de la
>> televisión local de Madrid en el que hay que hacer la palabra más
>> larga -válida- posible usando nueve letras escogidas al azar).

La parte de letras es muy fácil de hacer también. Básicamente se hace así:

Se coge un diccionario grande (en unix, el que usa ispell, por ejemplo).
Para cada palabra hacemos lo siguiente: se toman las letras de la
palabra, de forma individual, se ordenan por orden alfabético y se
eliminan duplicados. Seguidamente se guardan las palabras, usando como
clave la versión "modificada". Varias palabras pueden tener la misma clave.

Ejemplo, "oso" genera "os", "casa" genera "acs". "soso" genera "os"
también. "saca" genera "acs" también. Para cada clave, guardamos la
lista de palabras asociadas. Puede ser una o varias.

Una vez generada esa tabla, que solo se hace una vez, realizar un
"letras" es trivial:

1. Toma las letras que nos dan. Elimina duplicadas.

2. Genera todas las combinaciones de presencia/no presencia de cada
letra. Hay 2^n combinaciones. Osea, si hay 8 letras diferentes, hay
2^8=256 combinaciones.

3. Para cada combinación generada, ordena las letras resultantes por
orden alfabético. Busca la combinación en la tabla generada. Si no hay
coincidencia, no hay ninguna palabra con esas letras. Si hay un "hit",
comprobamos las palabras asociadas a esa clave.

- --
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea en argo.es http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
jabber / xmpp:jcea en jabber.org         _/_/    _/_/          _/_/_/_/_/
                               _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQCVAwUBRETr65lgi5GaxT1NAQK5UQP+MMx54AcBAIgM2oCWXrHq+A3WvvuOvxVS
KHviQtL8HiY6wUwO+DEHoYd/9kmBxZziCvA9OOuRlSuZ1zYaQYNYetfW5139XMX5
wc+1UQnoMlIHejmv8+LSCGGhgeHpK1NEKKh0/N2ReQEVmAmYDv0IjXCtCAPksDX1
m2ufDOytXN4=
=qBnW
-----END PGP SIGNATURE-----
------------ próxima parte ------------
_______________________________________________
Python-es mailing list
Python-es en aditel.org
http://listas.aditel.org/listinfo/python-es