webentwicklung-frage-antwort-db.com.de

Python: Verschachtelte 'for' - Schleifen

Ich möchte alle n-stelligen Zahlen durchgehen, so dass die zweite Ziffer der Zahl immer niedriger oder gleich der ersten ist, die dritte ist niedriger oder gleich der zweiten usw. Ich kann dies durch das Schreiben eines schrecklichen Codes wie folgt erhalten:

for i in range(10):
    for j in range(i+1):
        for k in range(j+1):

usw., aber mit 10-stelligen Zahlen sieht mein Code abscheulich aus, und das ist auch viel zu schreiben, und die Einrückung wird abscheulich, wenn ich einige davon empfehlen möchte. Gibt es einen schönen, prägnanten Weg, dies zu bekommen?

Edit: Nur damit die Leute wissen, warum ich mich damit beschäftige, https://projecteuler.net/problem=74 hat mir Nummern von 1 bis 1 Million überprüft. Leider ist es nicht so einfach, wie ich dachte - Zahlen mit führenden Nullen werden anders behandelt als Zahlen mit Nullen, sodass einige zusätzliche Magie durchgeführt werden musste. Vielen Dank an alle für aufschlussreiche Vorschläge.

16
098799

Könnte itertools verwenden:

>>> for comb in itertools.combinations_with_replacement(range(9, -1, -1), 3):
        print comb

(9, 9, 9)
(9, 9, 8)
(9, 9, 7)
(9, 9, 6)
...
(4, 0, 0)
(3, 3, 3)
(3, 3, 2)
(3, 3, 1)
(3, 3, 0)
(3, 2, 2)
(3, 2, 1)
(3, 2, 0)
(3, 1, 1)
(3, 1, 0)
(3, 0, 0)
(2, 2, 2)
(2, 2, 1)
(2, 2, 0)
(2, 1, 1)
(2, 1, 0)
(2, 0, 0)
(1, 1, 1)
(1, 1, 0)
(1, 0, 0)
(0, 0, 0)

Oder rekursiv, immer mehr Ziffern anhängen, bis genug genug vorhanden sind, wodurch int-Objekte anstelle von Zifferntupeln direkt erzeugt werden können (nicht sicher, ob das tatsächlich erforderlich ist):

def build(enough, prefix=0):
    if prefix >= enough:
        print(prefix)
        return
    for digit in range(prefix % 10 + 1) if prefix else range(1, 10):
        build(enough, prefix * 10 + digit)

Demo (Anmerkung "000" wird ausgelassen, nicht sicher, ob Sie das sowieso wollen):

>>> n = 3
>>> build(10**(n-1))
100
110
111
200
210
211
220
221
222
300
310
311
320
321
322
330
331
332
333
400
410
411
420
21
Stefan Pochmann

dies ist ein Ansatz, der itertools verwendet:

from itertools import combinations_with_replacement

N = 3

for kji in combinations_with_replacement((str(i) for i in range(10)), N):
    print(''.join(reversed(kji)))

beachten Sie, dass die Reihenfolge nicht der Ihres ursprünglichen Ansatzes entspricht.

ich hatte kürzlich eine ähnliche Frage ...

4

Ein einfacher rekursiver Ansatz:

def ordered_digits_generator(numDigits,min=1,max=9):
    for first in range(min,max+1):
        if numDigits == 1:
             yield first
        else:
             addend = first*10**(numDigits-1)
             for rest in ordered_digits(numDigits-1,min=0,max=first):
                 yield addend+rest

Dann aufgerufen über:

for number in ordered_digits_generator(10):
    print number

funktioniert wie erwartet.

Der Ansatz des Mathematikers

Das itertools-Paket enthält bereits eine Logik, die diese Rekursion im Wesentlichen bereits implementiert. Vermutlich besser als wir, mit umfangreichen Tests. So können wir es wie folgt verwenden:

import itertools
def ordered_digits_combo(numDigits):
    exponent = [10**i for i in range(0,numDigits)]

    for subset in itertools.combinations(range(0,numDigits+9),numDigits):
        if subset[numDigits-1]>numDigits-1:
            v = 0
            for i in range(0,numDigits):
                v += exponent[i]*(subset[i]-i)
            yield v

Bei einer bestellten Untermenge a[0]<a[1]<...<a[n-1] von {0,1,...,n+8} wählen wir die Nummer mit dem i austh Ziffer von rechts gleich a[i]-i. Wir müssen den Fall a[n-1]==n-1 ausschließen, da dies aus der Zahl mit allen Nullen besteht.

3
Thomas Andrews

Ich würde das wahrscheinlich rekursiv implementieren:

def generate(max, digits):
    for d in range(max + 1):
        if digits == 1:
            yield d
        else:
            first = d * 10**(digits-1)
            for n in generate(d, digits - 1):
                yield first + n

Die Ausgabe:

In : list(generate(3, 3))
Out:
[0,
 100,
 110,
 111,
 200,
 210,
 211,
 220,
 221,
 222,
 300,
 310,
 311,
 320,
 321,
 322,
 330,
 331,
 332,
 333]
0
Brandon Mintern

Ich habe den Vorschlag von @ iFlo so umgesetzt, wie er ursprünglich kommentiert wurde. Es ist nicht hypereffizient, aber es dauert sicherlich nicht ewig.

def digit_test(n):
    while n > 9:
        if (n % 100 / 10) < (n % 10): return False
        n /= 10
    return True

# under a second to construct a list of all numbers below 1000000 meeting the criteria
candidates = [x for x in xrange(1,1000000) if digit_test(x)]

# should be 8001 elements, consistent with other algorithms
print len(candidates)
0
brian_o