Sostituire cicli for innestati ... o no

Question

Ho uno script che scorre una serie di quattro (o meno) le stringhe di caratteri. Ad esempio:

aaaa
aaab
aaac
aaad

Se sono stati in grado di implementare con cicli for innestati in questo modo:

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)

E 'questo tipo di ciclo di nidificazione una brutta cosa, e in caso affermativo, quale sarebbe un modo migliore di realizzare quello che sto facendo?

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

Che ti stampare tutte le 15018570 le parole che stai cercando. Se volete più / meno parole basta cambiare il MAX_CHARS variabile. Si avrà ancora solo due for s per qualsiasi numero di caratteri, e non c'è bisogno di ripetere se stessi. Ed è abbastanza leggibile. .

Answer 2

ho intenzione di inviare la mia risposta come la più leggibile e meno scalabile:)

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: In realtà, questo non è corretto, in quanto produrrà i duplicati di tutte le stringhe di lunghezza <4. Rimuovere la stringa vuota dal chars matrice produrrebbe soltanto stringhe 4-char.

Normalmente mi piacerebbe cancellare questa risposta, ma ho ancora un po 'come se si bisogno di generare corde della stessa lunghezza.

Answer 3

scrittura per il programmatore prima -. Il secondo computer
Se è chiaro ed evidente a capire allora la sua corretta.

Se le questioni di velocità e il compilatore non ottimizzare comunque e, se lo si misura, ed è il problema - allora pensare a un modo più veloce intelligente

Answer 4

Non credo che sia una cosa negativa, a patto di capire (e documentare :-) esso. Non dubito ci può essere un modo più divinatorio o soluzione intelligente (con lambda o roba del genere), ma ho sempre privilegiato la leggibilità nel corso bravura.

Dal momento che è necessario generare tutte le possibilità di 1, 2, 3 e 4 caratteri "parole", questo metodo è buono come qualsiasi. Non sono sicuro di quanto tempo ci sarebbe voluto in quanto si sta efficacemente generando (molto approssimativamente) 14 milioni di linee di uscita (ma probabilmente ogni soluzione avrebbe avuto quel problema).

Pre-calcolando i prefissi comuni possono fornire un aumento di velocità, ma si starebbe meglio fuori misura per controllare ( sempre controllare, non assumere):

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: ho effettivamente fatto alcuni parametri di riferimento (con Windows Python 2.6.1) - questa versione dura circa 2,25 unità di tempo rispetto a quello originale 2,84 quindi è il 26% più veloce. Penso che potrebbe giustificare il suo utilizzo (di nuovo, fino a quando è documentato chiaramente che cosa sta cercando di realizzare).

Answer 5

@ di nosklo e @Triptych's producono risultati diversi:

>>> 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']

Ecco modificato @ soluzione del Trittico che producono lo stesso output del @ del 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

Ci sono molti algoritmi per la generazione di ogni permutazione di un set. Ciò che si vuole qui è un problema correlato, ma non direttamente analoga. Letture consigliate

Answer 7

Non è esattamente rispondere alla domanda, ma questo sarebbe tornato il n combinazione esimo per la data lunghezza e caratteri al massimo in alfabeto da usare:

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

Questo naturalmente ha senso solo se è necessario l'accesso casuale al set di combinazioni, invece di iterazione sempre attraverso tutti loro.

Se maxlen è alto, un po 'di ottimizzazione della velocità potrebbe essere raggiunto per esempio per sbarazzarsi di concatenazione di stringhe e ri-calcolare la lunghezza del alphabet e maxlen-1 ad ogni livello della ricorsione. Un approccio non ricorsivo potrebbe avere un senso, anche.