I am solving a recursion problem, where I am given an array of integers and asked to return the powerset of it.

e.g. powerset of [1,2,3] is [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Here is the recursive code that does it:

def powerset(array, idx = None): 
    if idx is None: 
        idx = len(array)-1 
    if idx <0: 
        return [[]]
    ele = array[idx]
    subset = powerset(array,idx-1) 
    for i in range(len(subset)): 
        currentSubset = subset[i]
        subset.append(currentSubset   [ele])
    return subset

While I do understand what is happening for the most part, my questions are:

1. when we get to the base case idx<0, this means the idx pointer points outside of the array, and we don't want to call array[idx], but my question is- do we return the empty set "[[]]" just as a filler, so that the top recursive call on the recursion stack gets executed next? Otherwise what does this do?

2. This might be a tallish order, but can someone explain with respect to the example [1,2,3] how the recursive call runs? Here is my understanding;

• We start with the pointer idx pointing at 3, so ele=3, we then initialise a subset called subset that holds the powerset of [1,2]

• Here is where I am confused, and struggling to see how the code pans out... Do we now go to the next batch of code which is the for loop? Or do we calculate the powerset of [1,2]?

CodePudding user response：

Adding print to the start and end of a recursive call is a useful way to visualize how it works.

def powerset(array, idx=None, indent=0):
    trace = f"{'  '*indent}powerset({array}, {idx})"
    print(f"{trace}...")
    if idx is None:
        idx = len(array)-1
    if idx < 0:
        print(f"{trace} -> [[]]")
        return [[]]
    ele = array[idx]
    subset = powerset(array, idx-1, indent 1)
    for i in range(len(subset)):
        subset.append(subset[i]   [ele])
    print(f"{trace} -> {subset}")
    return subset

prints:

powerset([1, 2, 3], None)...
  powerset([1, 2, 3], 1)...
    powerset([1, 2, 3], 0)...
      powerset([1, 2, 3], -1)...
      powerset([1, 2, 3], -1) -> [[]]
    powerset([1, 2, 3], 0) -> [[], [1]]
  powerset([1, 2, 3], 1) -> [[], [1], [2], [1, 2]]
powerset([1, 2, 3], None) -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Note that 0 and None need to be handled differently, which is why you need to use idx is None instead of not idx!

CodePudding user response：

As written, the function returns the power set of array[:idx 1] if it's passed an explicit index.

The test idx < 0 is really testing idx == -1, as other negative values should never occur. In this case, the function should compute the power set of the empty set, which is a set that contains one element: the empty set. The set containing the empty set is represented by [[]].

My impression is that you're trying to think of the recursive function as a loop written in a confusing way. You should instead just think of it as a function that computes something – in this case, a power set – and happens to use itself as a library function (in a way that always terminates).

Given a nonempty set S, which contains an element x, and a way to compute the power set of the smaller set S\{x}, how do you get the power set of S? Answer: for each set in the power set of S\{x}, return two sets: that set, and that set with x added to it. That's what this code does.