Reemplazar Bucles For Anidados... o no

Question

Tengo un script que se repite a través de una serie de cuatro (o menos) cadenas de caracteres.Por ejemplo:

aaaa
aaab
aaac
aaad

Si han sido capaces de implementar con bucles for anidados así:

chars = string.digits + string.uppercase + string.lowercase

for a in chars:
    print '%s' % a   
    for b in chars:
        print '%s%s' % (a, b)
        for c in chars:
            print '%s%s%s' % (a, b, c)
            for d in chars:
                print '%s%s%s%s' % (a, b, c, d)

Es este tipo de bucle de anidación de una cosa mala, y si es así, ¿cuál sería la mejor forma de llevar a cabo lo que estoy haciendo?

Answer 1

import string
import itertools

chars = string.digits + string.letters
MAX_CHARS = 4
for nletters in range(MAX_CHARS):
    for word in itertools.product(chars, repeat=nletters + 1):
        print (''.join(word))

Eso va a imprimir todos los 15018570 las palabras que usted está buscando. Si quieres más menos palabras / solo cambian el MAX_CHARS variable. Todavía tendrá sólo dos for s para cualquier número de caracteres, y usted no tiene que repetirse. Y es bastante fácil de leer. .

Answer 2

Voy a presentar mi respuesta como la más fácil de leer y menos escalable:)

import string
chars = [''] + list(string.lowercase)

strings = (a+b+c+d for a in chars
                   for b in chars
                   for c in chars
                   for d in chars)

for string in strings:
    print string

EDIT: En realidad, esto es incorrecto, ya que producirá duplicados de todas las cadenas de longitud <4. Extracción de la cadena vacía de la matriz chars acaba de producir cadenas 4-char.

Normalmente me borro esta respuesta, pero todavía un poco como si lo necesito para generar cadenas de la misma longitud.

Answer 3

Escribir para el programador primero -. El segundo equipo
Si es claro y evidente que entender entonces su correcta.

Si la velocidad es importante y el compilador no optimiza todos modos y si se lo mide y es el problema - y luego pensar en una manera más rápida inteligente

Answer 4

No creo que es una mala cosa, siempre que se entienda (y documento que :-). No cabe duda de que puede haber una manera más o Pythonic solución inteligente (con lambdas o lo que sea) pero siempre me ha favorecido la legibilidad sobre la inteligencia.

Ya que tienes que generar todas las posibilidades de 1-, 2-, 3- y 4 caracteres "palabras", este método es tan bueno como cualquier otro. No estoy seguro de cuánto tiempo se tardaría ya se está generando de manera efectiva (muy aproximadamente) 14 millones de líneas de salida (pero probablemente cada solución tendría ese problema).

Pre-calculando los prefijos comunes pueden proporcionar un impulso de velocidad, pero que sería mejor de medición para comprobar ( siempre cheque, no suponer):

chars = string.digits + string.uppercase + string.lowercase
for a in chars:
    print a
    for b in chars:
        ab = '%s%s' % (a, b)
        print ab
        for c in chars:
            abc = '%s%s' % (ab, c)
            print abc
            for d in chars:
                print '%s%s' % (abc, d)

EDIT: En realidad lo hice algunos puntos de referencia (con ventanas de Python 2.6.1) - esta versión toma alrededor de 2,25 unidades de tiempo en comparación con el original de 2.84 por lo que es 26% más rápido. Creo que podría justificar su uso (de nuevo, siempre y cuando se documenta claramente lo que está tratando de lograr).

Answer 5

y @ de nosklo https: / soluciones /stackoverflow.com/questions/482146/replace-nested-for-loops-or-not#482217">@Triptych's producen resultados diferentes:

>>> list(map(''.join, itertools.chain.from_iterable(itertools.product("ab", 
...     repeat=r) for r in range(4)))) # @nosklo's 

['', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', 'aab', 'aba', 'abb', 'baa', 
 'bab', 'bba', 'bbb']

>>> ab = ['']+list("ab")
>>> list(map(''.join, (a+b+c for a in ab for b in ab for c in ab)))  

['', 'a', 'b', 'a', 'aa', 'ab', 'b', 'ba', 'bb', 'a', 'aa', 'ab', 'aa', 
 'aaa', 'aab', 'ab', 'aba', 'abb', 'b', 'ba', 'bb', 'ba', 'baa', 'bab', 
 'bb',  'bba', 'bbb']

Aquí está modificado @ solución de tríptico que producen el mismo resultado que el de @ nosklo uno:

>>> ab = "ab"
>>> list(map(''.join, itertools.chain([''], ab, (a+b for a in ab for b in ab),
...     (a+b+c for a in ab for b in ab for c in ab))))

<*>

Answer 6

Hay muchos algoritmos para generar todas las permutaciones de un conjunto. Lo que se quiere aquí es un problema relacionado, pero no directamente análoga. Lecturas

Answer 7

No exactamente responder a la pregunta, pero esta iba a devolver el nth combinación de la longitud máxima de caracteres en el alfabeto a utilizar:

#!/usr/bin/python

def nth_combination(n, maxlen=4, alphabet='abc'):
    """
    >>> print ','.join(nth_combination(n, 1, 'abc') for n in range(3))
    a,b,c
    >>> print ','.join(nth_combination(n, 2, 'abc') for n in range(12))
    a,aa,ab,ac,b,ba,bb,bc,c,ca,cb,cc
    >>> import string ; alphabet = string.ascii_letters + string.digits
    >>> print ','.join(nth_combination(n, 4, alphabet) for n in range(16))
    a,aa,aaa,aaaa,aaab,aaac,aaad,aaae,aaaf,aaag,aaah,aaai,aaaj,aaak,aaal,aaam
    >>> print ','.join(nth_combination(n, 4, alphabet)
    ...                for n in range(0, 14000000, 10**6))
    a,emiL,iyro,mKz2,qWIF,u8Ri,zk0U,Dxav,HJi9,LVrM,P7Ap,UjJ1,YvSE,2H1h
    """
    if maxlen == 1:
        return alphabet[n]
    offset, next_n = divmod(n, 1 + len(alphabet)**(maxlen-1))
    if next_n == 0:
        return alphabet[offset]
    return alphabet[offset] + nth_combination(next_n-1, maxlen-1, alphabet)

if __name__ == '__main__':
    from doctest import testmod
    testmod()

Por supuesto, esto sólo tiene sentido si usted necesita el acceso aleatorio a el conjunto de combinaciones en lugar de iterar a través de todos ellos.

Si maxlen es alta, algunos optimización de la velocidad podría lograrse, por ejemplo,por deshacerse de la concatenación de cadenas y volver a calcular la longitud de alphabet y maxlen-1 en cada nivel de la recursividad.Un no-recursiva enfoque podría tener sentido, también.