Substitua laços for aninhados ... ou não

Question

Eu tenho um script que percorre uma série de quatro (ou menos) cordas personagens. Por exemplo:

aaaa
aaab
aaac
aaad

Se foram capazes de implementá-lo com aninhados loops assim:

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)

É este tipo de circuito nidificação uma coisa ruim, e em caso afirmativo, qual seria a melhor maneira de realizar o que estou fazendo?

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))

Isso vai imprimir todas 15018570 palavras que você está procurando. Se você quiser mais / menos palavras apenas mudar a variável MAX_CHARS. Ele ainda vai ter apenas dois fors para qualquer número de caracteres, e você não tem que repetir-se. E é muito legível. .

Answer 2

Vou apresentar a minha resposta como a escalável mais legível e menos:)

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: Na verdade, isso é incorreto, uma vez que irá produzir cópias de todas as cadeias de comprimento <4. Remover a cadeia vazia a partir da matriz chars seria apenas produzir cordas 4-carvão animal.

Normalmente eu apagar esta resposta, mas eu ainda meio que gosto disso, se você precisa gerar seqüências do mesmo comprimento.

Answer 3

Write para o programador primeiro -. O segundo computador
Se é claro e óbvio para entender, então é correto.

Se as coisas velocidade e o compilador não otimizá-lo de qualquer maneira e se você medi-lo e é o problema - depois pensar em uma maneira mais rápida inteligente

Answer 4

Eu não acho que é uma coisa ruim, desde que você entender (e documento :-)-lo. Não há dúvida de que pode ser uma maneira mais Python ou solução inteligente (com lambdas ou outros enfeites) mas eu sempre favoreceu a legibilidade sobre inteligência.

Uma vez que você tem para gerar todas as possibilidades de 1, 2, 3 e 4 caracteres "palavras", este método é tão bom quanto qualquer outro. Eu não tenho certeza quanto tempo que seria necessário desde que você está gerando efetivamente (muito aproximadamente) 14 milhões de linhas de saída (mas provavelmente cada solução teria esse problema).

Pré-cálculo dos prefixos comuns pode fornecer um impulso de velocidade, mas você seria melhor fora de medi-lo para verificar ( sempre cheque, não assumir):

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: Eu realmente fiz algumas referências (com janelas de Python 2.6.1) - esta versão leva cerca de 2,25 unidades de tempo em comparação com o original 2,84 por isso é 26% mais rápido. Eu acho que poderia justificar seu uso (mais uma vez, enquanto ele está documentado claramente o que ele está tentando alcançar).

Answer 5

de @ nosklo e @Triptych's soluções produzir 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']

Aqui está modificado @ solução do Tríptico que produzem a mesma saída como um do @ do nosklo:

>>> 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))))

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

Answer 6

Existem muitos algoritmos para gerar todas as permutações de um conjunto. O que você quer aqui é um problema relacionado, mas não diretamente análogo. Sugestões de leitura

Answer 7

Ele não responder exatamente a pergunta, mas este voltaria a combinação nth para o dado comprimento máximo e os caracteres em alfabeto para uso:

#!/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()

Isto, obviamente, só faz sentido se você precisa de acesso aleatório para o conjunto de combinações em vez de se iterar através de todos eles.

Se maxlen é alta, alguma otimização de velocidade poderia ser alcançado por exemplo por se livrar de concatenação e re-cálculo do comprimento do alphabet e maxlen-1 em cada nível de recursão. A abordagem não-recursiva pode fazer sentido, também.