Python: anidados ''para'' bucles

for-loop nested

Question

Me gustaría repasar todos los números de n dígitos, de modo que el segundo dígito del número siempre sea inferior o igual al primero, el tercero sea inferior o igual al segundo, etc. Puedo obtener esto escribiendo un código horrible como:

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

etc., pero con números de 10 dígitos, mi código se ve horrible, y eso también es mucha escritura, y la sangría se vuelve horrible si quiero felicitar a algunos de ellos. ¿Hay una forma agradable y concisa de conseguir esto?

Edición: solo para que la gente sepa por qué me molesto con esto, https://projecteuler.net/problem=74 me hace verificar los números de 1 a 1 millón. Desafortunadamente, no es tan sencillo como pensaba: los números con ceros a la izquierda se tratan de manera diferente a los que tienen ceros en el interior, por lo que hubo que realizar algo de magia adicional. De todos modos, gracias a todos por sus sugerencias perspicaces.

Answer 1

Este es un enfoque usando itertools :

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

tenga en cuenta que el orden no es el mismo que en su enfoque original.

Hace poco tuve una pregunta similar ...

Answer 2

Implementé la sugerencia de @ iFlo como se comentó originalmente. No es muy eficiente, pero ciertamente no lleva años.

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)

Answer 3

Podría usar itertools :

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

O recursivamente, agregando más y más dígitos hasta que sean suficientes, lo que puede producir más directamente objetos int lugar de tuplas de dígitos (no estoy seguro de si eso es lo que realmente necesita):

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)

Demostración (tenga en cuenta que omite " 000 ", no estoy seguro de si desea eso):

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

Answer 4

Probablemente implementaría esto recursivamente:

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

La salida:

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]

Answer 5

Un enfoque recursivo simple:

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

Luego se llama a través de:

for number in ordered_digits_generator(10):
    print number

Funciona como se espera.

El enfoque del matemático.

El paquete itertools ya tiene una lógica que esencialmente ya implementa esta recursión. Presumiblemente mejor que nosotros, con pruebas significativas. Así que podemos usarlo de la siguiente manera:

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

Dado un subconjunto ordenado a[0]<a[1]<...<a[n-1] de {0,1,...,n+8} , seleccionamos el número con el i dígito de la derecho igual a a[i]-i . Tenemos que excluir el caso a[n-1]==n-1 porque consiste en el número con todos los ceros.