Блог

Я пытаюсь понять стек вызовов для приведенной ниже рекурсивной функции python. Функция выдает все комбинации для данного набора.

 def subsets(A):
    if not A:
        yield []
    else:
        for s in subsets(A[1:]):
            yield s
            yield [A[0]]   s
l1=[1,2,3]
print(list(subsets(l1)))
  

Программа генерирует выходные данные по желанию:

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

Однако я не могу визуализировать стек вызовов. Как он может печатать [1,2,3] ?
Насколько я понимаю, следующим образом

 call stack 1 : values are : for s in [2,3], a[0] = 1, a = [1,2,3]
call stack 2 : values are : for s in [3], a[0] = 2, a = [2,3]
call stack 3 : values are : for s in [], a[0] = 3, a = [3]
  

Может ли кто-нибудь помочь мне понять поток стека вызовов со s a значениями и?

При susbsets первоначальном вызове аргумент A равен [1, 2, 3] . Важно отметить, что функция будет повторно вызывать себя с аргументами [2, 3] , [3] и [] прежде чем она начнет выдавать значения для текущего аргумента, [1, 2, 3] . Затем все эти рекурсивные вызовы возвращаются, и мы выполняем следующий код со A значением [1, 2, 3] :

 for s in subsets(A[1:]):
    yield s # produces [2, 3]
    yield [A[0]]   s # produces [1, 2, 3]
  

Таким образом, мы ожидаем, что последние два полученных значения будут находиться [2, 3], [1, 2, 3] в пределах содержащего списка.

Это прямая реализация математического определения набора полномочий

Пустой A не имеет подмножеств ( yield [] ).

Для непустого у вас есть два варианта

1. сохраните первый элемент и объедините все возможные подмножества остальных (yield [A[0]] s)

2. не сохраняйте первый элемент и возвращайте возможные подмножества остальных ( yield s )

Итак, у A = [1, 2, 3] вас есть объединение [1] subsets([2, 3]) и subsets([2, 3]) . Аналогично, subsets([2, 3]) это объединение [2] subsets([3]) и subsets([3]) . наконец, subsets([3]) это [] или [3] . Это дает 3 шага с 2 возможными результатами для каждого, что дает 8 возможных комбинаций.

Вы вызываете list() генератор. Это приведет к вызову генератора снова и снова, пока он не будет исчерпан. Давайте проследим за ходом выполнения. Это может быть хорошим упражнением для понимания генераторов. Я отформатирую все в виде блока кода, чтобы я мог использовать правильные отступы для уточнения иерархии вызовов генератора.

 subsets([1, 2, 3]) is called, 
    so A is [1, 2, 3]. 
    This list is not empty, so the else block is executed.
    A[1:] is [2, 3], so to determine the first s,
    subsets([2, 3]) is called.
        Now A is [2, 3], so A[1:] is [3], so to determine s,
        subsets([3]) is called.
            Now A is [3], so A[1:] is [], so to determine s,
            subsets([]) is called.
                Now A is [], so the if block is executed.
                This yields [].
            The loop starts with s = [].
            This yields [] again.
        Now this loop starts, also with s = [],
        because this is what subsets([3]) has just yielded.
        So this yields [] as well.
    So subsets([2, 3]) has yielded [], 
    so this loop also starts with s = [].
    This yields [] yet again.
So subsets([1, 2, 3]) has yielded [], 
and now this generator is called again (because of list()), 
    picking up the action after the previously executed yield statement.
    So we reach the next statement: yield [A[0]]   s.
    This yields [1].
subsets([1, 2, 3]) is called again,
    picking up at the end of the first run through the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again, 
        picking up at yield [A[0]]   s.
        This yields [2].
    So the loop starts again, with s = [2].
    This yields [2].
subsets([1, 2, 3]) is called again,
    picking up at yield [A[0]]   s, with s = [2].
    This yields [1, 2].
subsets([1, 2, 3]) is called again,
    picking up at the end of the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again,
        picking up at the end of the for loop,
        so to determine the next s,
        subsets([3]) is called again, 
            picking up at yield [A[0]]   s.
            This yields [3].
        So the loop starts again, with s = [3].
        This yields [3].
    So the loop starts again, with s = [3].
    This yields [3].
subsets([1, 2, 3]) is called again,
    picking up at yield [A[0]]   s, with s = [3].
    This yields [1, 3].
subsets([1, 2, 3]) is called again,
    picking up at the end of the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again,
        picking up at yield [A[0]]   s, with s = [3].
        This yields [2, 3].
    So the loop starts again, with s = [2, 3].
    This yields [2, 3]. 
subsets([1, 2, 3]) is called again,
    picking up at yield [A[0]]   s, with s = [2, 3].
    This yields [1, 2, 3].
subsets([1, 2, 3]) is called again,
    picking up at the end of the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again,
        picking up at the end of the for loop,
        so to determine the next s, 
        subsets([3]) is called again, 
            picking up at the end of the for loop,
            so to determine the next s, 
            subsets([]) is called again, 
                picking up at the end of the if block,
                so we reach the end of the generator, 
                which means it is exhausted and yields nothing anymore.
            So there is no further iteration of the for loop,
            hence subsets([3]) is also exhausted.
        So subsets([2, 3]) is also exhausted.
    So subsets([1, 2, 3]) is also exhausted.