Как мне реализовать этот кусок python кода с помощью рекурсии? - PullRequest
Новая
       6

Как мне реализовать этот кусок python кода с помощью рекурсии?

0 голосов
/ 10 апреля 2020

Я пытаюсь найти рекурсивный способ сделать это, передав число для циклов в рекурсивной функции: 

def non_recursive():
  combinations = []

  for i in range(2): # first character
    for j in range(2): # second character
      for k in range(2): # third character
        combinations.append([i, j, k])

  return combinations

print(non_recursive())

Вывод: 

[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

В этом примере использовались 3 для петель. Прототип функции для рекурсивного способа должен выглядеть следующим образом: 

def recursive(number_of_iterations): # number of iterations = length of each list
  # implementation goes here!

Как новичок, я понятия не имею, как подойти к этому. Если кто-то может помочь, я действительно ценю это!

1 Ответ

2 голосов
/ 11 апреля 2020

Вы должны объединить каждый результат из рекурсивного (n-1) с [0] и с [1]:

Вот пример использования двухуровневого понимания списка: 

def recursive(n):
    if n == 1: return [[0],[1]]
    return [ r+[b] for r in recursive(n-1) for b in [0,1] ]


print(recursive(3))

# [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Эти типы комбинаторных c функций, однако, обычно определяются как генераторы, так что результаты могут обрабатываться без необходимости генерировать и хранить все значения в большом списке: 

def recursive(n):
    if n == 1:
        yield [0]
        yield [1]
    else:
        for r in recursive(n-1):
            yield r+[0]
            yield r+[1]

for combo in recursive(3): print(combo)

[EDIT] Вы можете обобщить это далее, предоставив (переменные) размеры диапазона в качестве параметров: 

def multiRange(n,*rest):
    for i in range(n):
        for r in multiRange(*rest) if rest else [tuple()]:
            yield (i,)+r

output: 

for x,y,z in multiRange(2,3,2):
    print((x,y,z))

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(0, 2, 0)
(0, 2, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
(1, 2, 0)
(1, 2, 1)

это было бы полезно, чтобы получить все координаты многомерной матрицы (или списка списков)

Может использоваться с распаковкой параметров для вашего конкретного примера c: 

for combo in multiRange(*[2]*3): print(combo)

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
...