Ersetzen Verschachtelte For-Schleifen ... oder nicht

Question

Ich habe ein Skript, das durch eine Reihe von vier (oder weniger) Zeichenketten-Schleifen. Zum Beispiel:

aaaa
aaab
aaac
aaad

Wenn der Lage gewesen, es mit verschachtelten zu implementieren für Schleifen wie folgt:

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)

Ist diese Art der Schleife eine schlechte Sache nisten, und wenn ja, was für eine bessere Art und Weise zu bewerkstelligen wäre, was ich tue?

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

Das wird drucken Sie alle 15018570 Wörter Sie suchen. Wenn Sie mehr / weniger Wörter ändern, nur die MAX_CHARS Variable. Es wird nach wie vor nur zwei fors für eine beliebige Anzahl von Zeichen haben, und Sie müssen nicht selbst wiederholen. Und ist ziemlich lesbar. .

Answer 2

Ich werde meine Antwort als die lesbar und am wenigsten skalierbare einreichen:)

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: Eigentlich ist dies falsch, da es Duplikate aller Strings der Länge produzieren <4. Das Entfernen der leeren String aus dem chars Array erzeugen würde nur 4-char-Strings.

Normalerweise würde ich diese Antwort löschen, aber ich mag es immer noch ein bisschen, wenn Sie brauchen Zeichenketten der gleichen Länge zu erzeugen.

Answer 3

Schreiben für den Programmierer zuerst -. Der Computer zweiten
Wenn es klar und deutlich zu verstehen, dann sein richtig.

Wenn die Geschwindigkeit Angelegenheiten und die Compiler optimieren nicht es trotzdem und wenn man es messen und es ist das Problem - dann denken Sie an einem schnellen cleveren Weg

Answer 4

Ich glaube nicht, es ist eine schlechte Sache, vorausgesetzt, Sie verstehen (und Dokument :-) es. Ich zweifle nicht, kann es zu einer mehr pythonic Weg oder clevere Lösung (mit Lambda-Ausdrücke oder Dingsbums), aber ich habe immer die Lesbarkeit über Klugheit begünstigt.

Da Sie alle Möglichkeiten von 1- zu erzeugen haben, 2-, 3- und 4-Zeichen „Wörter“, ist diese Methode so gut wie jeder andere. Ich bin mir nicht sicher, wie lange es dauern würde, da Sie effektiv sind zu erzeugen (sehr grob) 14 Millionen Zeilen der Ausgabe (aber wahrscheinlich würde jede Lösung dieses Problem hat).

die gemeinsamen Präfixe Pre-Berechnung kann einen Geschwindigkeitsschub sorgen, aber sie würde besser dran messen, es zu überprüfen ( immer überprüfen, nie übernehmen):

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: Ich habe tatsächlich einige Benchmarks (bei Windows-Python 2.6.1) - diese Version etwa 2,25 Zeiteinheiten im Vergleich zum ursprünglichen 2,84 nimmt also 26% schneller ist. Ich denke, dass seine Verwendung rechtfertigen könnte (wieder, solange es klar dokumentiert ist, was es versucht zu erreichen).

Answer 5

@ nosklo der und @Triptych's Lösungen zu unterschiedlichen Ergebnissen führen:

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

Hier @ Triptychon-Lösung modifiziert, dass die gleiche Ausgabe wie die @ nosklo eint produzieren:

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

Es gibt viele Algorithmen für jede Permutation eines Satzes zu erzeugen. Was Sie wollen, ist hier ein ähnliches Problem, aber nicht direkt analog. Empfohlene Literatur

Answer 7

Es ist nicht genau beantwortet die Frage, aber diese die nth Kombination für die gegebenen maximale Länge und Zeichen im Alphabet zu verwenden zurückkehren würden:

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

Das macht natürlich nur Sinn, wenn man statt immer Iterieren auf den Satz von Kombinationen Direktzugriff benötigen, um durch sie alle.

Wenn maxlen hoch ist, könnten einige Geschwindigkeitsoptimierung beispielsweise erreicht werden, durch Verkettung des Strings Loswerden und erneut Berechnen der Länge des alphabet und maxlen-1 auf jeder Ebene der Rekursion. Ein nicht-rekursive Ansatz könnte Sinn machen, auch.