Получение всех результатов рекурсии в списке

Question

Я изучаю рекурсию Python. На практике я даю задачу найти все подмножество списка. Например, функция:

subset([1,2)] should return [[1,2],[1],[2],[]]

Я могу заставить свою функцию распечатать эти результаты с помощью рекурсии

def subset(List):
   print(List)
   n = len(List)
   if n > 2:
      for i in range(n):
         subset(List[:i]+List[i+1:])

   if n == 2:
      subset([List[0]])
      subset([List[1]])
   if n == 1:
      subset([])
pass

L = [1,2]
test = subset(L)

Оператор print печатает:

[1, 2], [1], [], [2], []

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

Мне бы очень хотелось, чтобы вы взялись за это.

Answer 1

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

Но это интересная проблема для изучения рекурсии, поэтому давайте возьмем

Аналогично здесь , для сложных случаев использования рекурсии, которые а) делают несколько рекурсивных вызовов одновременно и б) должны каким-то образом "накапливать" результаты, мойРекомендую написать рекурсивный генератор. Вы можете преобразовать его механически:

• заменить print на yield

• yield from рекурсивные вызовы (как я отметил надругой ответ там, для случаев, когда вам не нужно накапливать результаты, вы, как правило, хотели бы return эти).

Затем из-за пределов рекурсии вы можете собрать результатыв list, или итерируйте их напрямую.

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

• Рекурсивно получить подмножества, не включающие в себя первый элемент
• Для каждого из них выведите два результата: один с добавленным первым элементом иодин без

Так что вместо yield from мы будем перебирать результаты, делать некоторые изменения и yield внутри этого цикла.

Собирая все это вместе, похоже:

def power_set(items):
    if not items: # empty set; base case for recursion.
        yield items
        return
    # Pull off the first element,
    first, *rest = items
    # then iterate over the recursive results on the rest of the elements.
    for without_first in power_set(rest):
        yield [first] + without_first
        yield without_first

# let's test it:
list(power_set([1,2,3]))
# [[1, 2, 3], [2, 3], [1, 3], [3], [1, 2], [2], [1], []]
# Good, just what we want - with no duplicates.