Как я могу динамически добавлять n вложенных циклов for, используя рекурсию: - PullRequest
Новая
       38

Как я могу динамически добавлять n вложенных циклов for, используя рекурсию:

1 голос
/ 05 мая 2020

Я хотел бы динамически добавить N вложенных циклов for, если возможно, используя рекурсию, следуя этому шаблону в этом коде: 

 Total = 4
 counter = 0
 for i in range(1, Total + 1):
     for j in range(i + 1, Total + 1):
         for k in range(j + 1, Total + 1):
             print(i, j ,k)
             counter += 1
 print(f"Number of combinations: {counter}")

На выходе будут все комбинации из 3 чисел в общей сложности 4 числа (1, 2, 3, 4) в отсортированном порядке с общим количеством результатов: 

1 2 3
1 2 4
1 3 4
2 3 4
Number of combinations: 4

Вот моя мотивация, я хочу динамически увеличивать длину комбинаций.

Мне бы понравилось что-то вроде Total choose N elements (где N равно количеству вложенных циклов for в этом шаблоне), и единственный способ, который я нашел для этого, - это жесткое кодирование N вложенных циклов for с предыдущим шаблоном.

Я попытался реализовать это самостоятельно, задав несколько аналогичных вопросов по stackoverflow, но мне не удалось создать циклы for с использованием рекурсии, с желаемым шаблоном, а itertools combinations не работают если мне нужно что-то вроде a combination of 15 elements(set of length 15) from 25 in total, как показано ниже: 

#Adapted from https://www.geeksforgeeks.org/permutation-and-combination-in-python/
# A Python program to print all
# combinations of given length
from itertools import combinations
Total = 25
n = 15
counter = 0
# Get all combinations of [1,2,3..25]
# and length n
comb = combinations([i for i in range(1, Total + 1)], n)

# Print the obtained combinations
for i in list(comb):
    print(i)
    counter += 1
print(f"Number of combinations: {counter}")

Ожидаемый результат: 

               1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
               1 2 3 4 5 6 7 8 9 10 11 12 13 14 16
               1 2 3 4 5 6 7 8 9 10 11 12 13 14 17
                              ...
               10 12 13 14 15 16 17 18 19 20 21 22 23 24 25
               11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
               Number of combinations:  3.268.760

Фактический результат: Killed, но если жесткий код, как показано ниже, он работает довольно хорошо и дает де sired output: 

def main():
    counter = 0
    for a in range (1, 26,1):
        for b in range (a + 1, 26,1):
            for c in range (b + 1, 26,1):
                for d in range (c + 1, 26,1):
                    for e in range (d + 1, 26,1):
                        for f in range (e + 1, 26,1):
                            for g in range (f + 1, 26,1):
                                for h in range (g + 1, 26,1):
                                    for i in range (h + 1, 26,1):
                                        for j in range (i + 1, 26,1):
                                            for k in range (j + 1, 26,1):
                                                for l in range (k + 1, 26,1):
                                                    for m in range (l + 1, 26,1):
                                                        for n in range (m + 1, 26,1):
                                                            for o in range (n + 1, 26,1):
                                                                print(a, b, c, d, e, f, g, h, i, j, k, l, m , n, o)
                                                                counter += 1
    print(f"Number of combinations: {counter}")
main()

Однако я не могу увеличивать и уменьшать набор комбинаций по мере необходимости. Было бы неплохо получить это, динамически увеличивая и уменьшая количество вложенных циклов for. * Спасибо людям за отзыв

1 Ответ

0 голосов
/ 06 мая 2020
Метод

itertools.combinations у меня работает нормально. У вас могут возникнуть проблемы с памятью, если вы запускаете его на виртуальной машине / docker контейнере с небольшим объемом памяти. Python целые числа занимают 24 байта, поэтому вам понадобится как минимум 74,8 МБ (24 * 3268760) памяти, плюс служебные данные списка (около 25 МБ) для хранения списка.

Обратите внимание, что list(comb) будет пытаться заранее вычислить все комбинации и потреблять память. Учебник, который вы читали, неправильный. Вы должны напрямую использовать итератор, т.е. 

...
for i in comb:
    print(i)
    counter += 1
print(f"Number of combinations: {counter}")

Если вы указываете только количество элементов, вы можете использовать этот трюк, чтобы сделать его короче: 

counter = sum(1 for item in comb)
print(f"Number of combinations: {counter}")
...