Logical Bug in the Code Related to Slicing in Python

Question

Consider the following piece of code that generates all subsets of size k of an array [1,2,3,...,n]:

def combinations(n, k):
   result = []
   directed_combinations(n, k, 1, [], result)
   return result

def directed_combinations(n, k, offset, partial_combination, result):
    if len(partial_combination) == k:
        new_partial = [x for x in partial_combination]
        result.append(new_partial)
        return
    num_remaining = k - len(partial_combination)
    i = offset
    #                kind of checks if expected num remaining is no greater than actual num remaining
    while i <= n and num_remaining <= n - i + 1:
        partial_combination.append(i)
        directed_combinations(n, k, i + 1, partial_combination, result)
        del partial_combination[-1]
        # partial_combination = partial_combination[:-1] <-- same funcationality as line above, but produces weird bug.
        i += 1

print(combinations(n=4,k=2))

For example, combinations(n=4,k=2) will generate all subsets of length 2 of [1,2,3,4]. There are two lines in the code that produce a list with the last element removed. I tried accomplishing it with del and creating a brand new list by slicing off the last element (i.e. [-1]). The version with del produces the correct result. But, version with [-1] doesn't. There is no runtime error; just a logical bug (i.e. incorrect result).

I suspect this has something to do with creating a new list when doing slicing vs. keeping the same list with del. I can't seem to understand why this is an issue.

Andras Deak -- Слава Україні · Accepted Answer · 2016-12-20 22:49:31Z

4

I didn't notice at first that your function is recursive (should've read your tags better).

You're right, functionally the two are almost the same. Here is the exact same thing:

# del partial_combination[-1]                     # working (mutate)
# partial_combination = partial_combination[:-1]  # different (rebind)
partial_combination[:] = partial_combination[:-1] # same (mutate)

The result of each of the above will be that you end up with a list containing the same elements. But while del and partial_combination[:] mutate your original list, the middle one rebinds the name to a new list with the same elements. When you pass on this new list to the next recursive step, it will operate on its own copy rather than on the single list the previous recursive levels are working on.

To prove this, you can call print(id(partial_combination)) after each of the above options, and see that the id changes in the rebinding case, while it stays the same throughout the mutating ones.

answered Dec 20, 2016 at 22:49

Andras Deak -- Слава Україні

35.4k13 gold badges94 silver badges118 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Aza T Over a year ago

Okay. It makes sense. However, at first, I was confused why the last option mutated the list rather than creating a new one. I've never seen assignment to slices before. Checking the docs (3.1.3 section) clarified it for me.

Andras Deak -- Слава Україні Over a year ago

@AzaTulepbergenov here's an additional source for understanding mutating vs rebinding.

Collectives™ on Stack Overflow

Logical Bug in the Code Related to Slicing in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related