Альтернатива вложенным циклам

Question

Возьмите этот код, например,

#Find all combinations of five positive integers whose reciprocals sum to 1 under a limit
limit = 30
none = True
reciprocals5 = []
for x in range(1,limit):
    for y in range(1,limit):
        for z in range(1,limit):
            for a in range(1,limit):
                for b in range(1,limit):
                    if(x!=y and x!=z and x!=a and x!=b and y!=z and y!=a and y!=a and y!=b and z!=a and z!=b and a!=b):
                        if(1/x + 1/y + 1/z + 1/a + 1/b == 1):
                            reciprocals5.append([x,y,z,a,b])
                            none = False

Если бы мне нужно было найти все 6 положительных целочисленных комбинаций, мне пришлось бы добавить еще l oop и так далее. Допустим, я хочу найти все N положительных целочисленных комбинаций. Поскольку я не могу создать N вложенных для циклов, какова альтернатива?

Answer 1

Поскольку я не могу создать N вложенных для циклов, что является альтернативой?

Рекурсия!

Имеет функцию, принимающую дополнительные аргументы, например количество членов для суммирования и целевого числа, затем при его реализации вызовите себя снова с одним меньшим числом членов.

Ваше условие остановки - когда число слагаемых для суммирования равно нулю. В этом случае, если целевое число, которое нужно достичь, равно нулю, это означает, что вы нашли правильную сумму. Если оно ненулевое, значит, нет. (Точно так же вы можете выполнить последнюю проверку за 1 семестр слева, проверяя, можете ли вы выбрать последнее число, соответствующее ему.)

Поскольку вам нужно найти только наборы различных чисел, которые суммируя до одного, вы можете принять x> y> z> a> b (или обратный порядок), чтобы убедиться, что вы не находите одну и ту же последовательность снова и снова, просто в другом порядке.

Кроме того, итерация вниз от лимита означает, что обратные связи будут расти по мере того, как вы продолжите итерацию. Это также означает, что вы можете перестать смотреть, как только сумма превысит единицу (или цель станет отрицательной), что должно помочь вам быстро сократить циклы, которые никогда не приведут к новым значениям.

Наконец, Python также поддерживает дроби , что означает, что вы можете выполнять эти вычисления с точной точностью, не беспокоясь о проблемах округления чисел с плавающей запятой.

Собирая все вместе:

from fractions import Fraction

def reciprocal_sums(n=5, limit=30, target=1, partial=()):
    if n == 0:
        if target == 0:
            yield partial
        return
    for i in range(limit, 0, -1):
        new_target = target - Fraction(1, i)
        if new_target < 0:
            return
        yield from reciprocal_sums(
            n - 1, i - 1, new_target, partial + (i,))

Тестирование для n = 5 (по умолчанию):

>>> list(reciprocal_sums())
[(30, 20, 12, 3, 2),
 (30, 20, 6, 4, 2),
 (30, 10, 6, 5, 2),
 (28, 21, 12, 3, 2),
 (28, 21, 6, 4, 2),
 (28, 14, 7, 4, 2),
 (24, 12, 8, 4, 2),
 (20, 12, 6, 5, 2),
 (20, 6, 5, 4, 3),
 (18, 12, 9, 4, 2),
 (15, 12, 10, 4, 2)]

для n = 4:

>>> list(reciprocal_sums(4))
[(24, 8, 3, 2),
 (20, 5, 4, 2),
 (18, 9, 3, 2),
 (15, 10, 3, 2),
 (12, 6, 4, 2)]

и n = 6:

>>> list(reciprocal_sums(6))
[(30, 28, 21, 20, 3, 2),
 (30, 24, 20, 8, 4, 2),
 (30, 24, 10, 8, 5, 2),
 (30, 20, 18, 9, 4, 2),
 (30, 20, 15, 10, 4, 2),
 (30, 18, 10, 9, 5, 2),
 (30, 12, 10, 5, 4, 3),
 (28, 24, 21, 8, 4, 2),
 (28, 21, 20, 6, 5, 2),
 (28, 21, 18, 9, 4, 2),
 (28, 21, 15, 10, 4, 2),
 (28, 20, 14, 7, 5, 2),
 (28, 14, 12, 7, 6, 2),
 (28, 14, 7, 6, 4, 3),
 (24, 20, 12, 8, 5, 2),
 (24, 20, 8, 5, 4, 3),
 (24, 18, 9, 8, 6, 2),
 (24, 15, 10, 8, 6, 2),
 (24, 12, 8, 6, 4, 3),
 (20, 18, 12, 9, 5, 2),
 (20, 18, 9, 5, 4, 3),
 (20, 15, 12, 10, 5, 2),
 (20, 15, 10, 5, 4, 3),
 (18, 15, 10, 9, 6, 2),
 (18, 12, 9, 6, 4, 3),
 (15, 12, 10, 6, 4, 3)]

Это решение довольно быстрое , Работа на процессоре Snapdragon 845 ARM:

%timeit list(reciprocal_sums(4)) 
365 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(reciprocal_sums(5))
1.94 s ± 8.93 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(reciprocal_sums(6))
8.26 s ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Упорядочение (понижение лимита на каждом уровне) вместе с сокращением последних уровней после достижения уровня выше, сделает это решение намного быстрее, чем те, которые оценивают все возможные перестановки или комбинации.

Answer 2

Вы можете использовать itertools.permutations.

import itertools

reciprocals = []
for x in itertools.permutations(range(1, limit), N):
    if sum(1/i for i in x) == 1:
        reciprocals.append(x)

Answer 3

Попробуйте:

import itertools
myList = []
for combination in itertools.product(range(10), repeat=6):
    myList.append(''.join(map(str, combination)))

Это создаст список из 6 целых чисел di git в формате str. Вы можете легко набрать бросок.

Answer 4

itertools.product(list(range(N)),repeat=N)

возможно, что вы хотите