How [‘STANFORD’] is retrieved from pswf

Hi. I am really having trouble understanding how [‘STANFORD’] is retrieved from pswf (power_set_without_first) given that the function recurses with the original list each time, just without the first item (my_list[1:]).

Here is my logic for pswf when the list is [‘UCLA’, ‘STANFORD’, ‘NYU’]: Function is invoked with this list and then reaches “power_set_without_first = power_set(my_list[1:])” . So this function must now call [‘STANFORD’, ‘NYU’] and thus it it placed on the call_stack.

The power_set function is now invoked with [‘STANFORD’, ‘NYU’] and reaches the same line again “power_set_without_first = power_set(my_list[1:])” which calls [‘NYU’] thus this is placed on the call_stack. The recurses and retrieves the base case of [empty].

As you can see, when the list is [‘UCLA’, ‘STANFORD’, ‘NYU’] I am only able to see how psfw retrieves:
[[‘STANFORD’, ‘NYU’], [‘NYU’], [empty]] and not [[‘STANFORD’, ‘NYU’], [‘STANFORD’], [‘NYU’], [empty]] like the the solution in the module states.

I know I am missing something here, but any thoughts to help me understand this? I am thinking that [‘STANFORD’, ‘NYU’] must call both [‘STANFORD’] and [‘NYU’] but am unsure of how/why given that it is still a recursive function.

1 Like

Actually I added print statements and changed the list to numbers to make it more straightforward and I see whats happening here.

def power_set(my_list):

if len(my_list) == 0:
return []

power_set_without_first = power_set(my_list[1:])
print (“pswf:”)
print (power_set_without_first)

with_first = [ [my_list[0]] + rest for rest in power_set_without_first ]
print (“wf:”)
print (with_first)

print (“wf + pswf:”)
print (with_first + power_set_without_first)
return with_first + power_set_without_first

numbers = [“1”, “2”, “3”]

power_set_of_numbers = power_set(numbers)

print (" ")
print (“Result:”)

for set in power_set_of_numbers:
print(set)

RESULT:

pswf:
[]
wf:
[[‘3’]]
wf + pswf:
[[‘3’], ]
pswf:
[[‘3’], ]
wf:
[[‘2’, ‘3’], [‘2’]]
wf + pswf:
[[‘2’, ‘3’], [‘2’], [‘3’], ]
pswf:
[[‘2’, ‘3’], [‘2’], [‘3’], ]
wf:
[[‘1’, ‘2’, ‘3’], [‘1’, ‘2’], [‘1’, ‘3’], [‘1’]]
wf + pswf:
[[‘1’, ‘2’, ‘3’], [‘1’, ‘2’], [‘1’, ‘3’], [‘1’], [‘2’, ‘3’], [‘2’], [‘3’], []]

Which is the expected result.

So the stack looks like this from top to bottom [ ‘’, ‘[3]’, ‘[2], [3]’, ‘[1], [2], [3]’] So for some reason it is popping the top item of the “power_set_without_first = power_set(my_list[1:])” stack which is an empty list, , and using that as the base input for “with_first”.

Then “with_first” uses the previous item in the stack, [3], as [my_list[0]] giving us [[‘3’], ] for “pswf + wf”.

The function then uses this as the new pswf. “with_first” then recurses one place further down the call stack, and coincidentally the list, to [2]. So “[2] + rest for rest in pswf” = wf = [2,3] and [2]. So pswf + wf = [[‘2’, ‘3’], [‘2’], [‘3’], ] and this becomes the new pswf. So we move down the list once again to [1] and wf = [[‘1’, ‘2’, ‘3’], [‘1’, ‘2’], [‘1’, ‘3’], [‘1’]]. And so on and so on

1 Like