Python: вложенные петли for

Я бы хотел пройти все n-значные числа, чтобы вторая цифра числа всегда была ниже или равна первой, третья - ниже или равна второй и т.д. Я могу получить это, написав ужасный код например:

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

и т.д., но с 10-значными номерами мой код начинает выглядеть ужасно, а также, что много писем и отступов становятся ужасными, если я хочу поблагодарить немногих из них. Есть ли хороший, лаконичный способ получить это?

Изменить: просто чтобы люди знали, почему я беспокоюсь об этом, https://projecteuler.net/problem=74 имеет чек от 1 до одного миллиона. К сожалению, это не так прямолинейно, как я думал - цифры с ведущими нулями обрабатываются иначе, чем те, у которых есть нули внутри, поэтому нужно было выполнить некоторую дополнительную магию. В любом случае, спасибо всем за проницательные предложения.

Ответы

Ответ 1

Можно использовать 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)

Или рекурсивно, добавляя все больше и больше цифр до тех пор, пока не получится достаточно, чтобы более непосредственно создавать объекты int вместо цифровых кортежей (не уверен, что вам действительно нужно):

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)

Демонстрация (обратите внимание, что это исключает "000", не уверен, хотите ли вы этого):

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

Ответ 2

этот подход использует 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)))

обратите внимание, что порядок не совпадает с вашим первоначальным подходом.

Недавно у меня был вопрос simliar...

Ответ 3

Простой рекурсивный подход:

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

Затем вызывается через:

for number in ordered_digits_generator(10):
    print number

работает как ожидалось.

Математический подход

Пакет itertools уже имеет логику, которая по существу уже реализует эту рекурсию. Предположительно лучше, чем мы можем, со значительным тестированием. Поэтому мы можем использовать его следующим образом:

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

Для упорядоченного подмножества a[0]<a[1]<...<a[n-1] of {0,1,...,n+8} мы выбираем число с цифрой я ^th справа от a[i]-i. Мы должны исключить случай a[n-1]==n-1, поскольку он состоит из числа со всеми нулями.

Ответ 4

Я внедрил предложение @iFlo, как было прокомментировано изначально. Он не является гиперэффективным, но, конечно же, он не принимает возрастов.

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)

Ответ 5

Я бы, вероятно, реализовал это рекурсивно:

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

Выход:

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]