CODEWITHSUNDEEP
python
M3RS
M3RS

Reputation: 7500

Python: using append within recursive function - overwrites previous elements

Could someone explain how to fix the below? I've read some explanations, but couldn't get my head around it...

Many thanks in advance!

k = 2                  # number of possible values for each element, in this case 0 or 1
length = 3             # length of list
result = [0] * length  # initialise list
results = []

# generate permutations of list
def permutations(i, k, length):
    j = 0
    while j < k:
        result[i] = j
        if i == length - 1:
            print("Result: ", result)
            results.append(result)
            print("Results: ", results)
        else:
            permutations(i + 1, k, length)
        j += 1

permutations(0, k, length)

Below the output. The problem is that all previous elements in the list are overwritten...

Result:  [0, 0, 0]
Results:  [[0, 0, 0]]
Result:  [0, 0, 1]
Results:  [[0, 0, 1], [0, 0, 1]]
Result:  [0, 1, 0]
Results:  [[0, 1, 0], [0, 1, 0], [0, 1, 0]]
Result:  [0, 1, 1]
Results:  [[0, 1, 1], [0, 1, 1], [0, 1, 1], [0, 1, 1]]
Result:  [1, 0, 0]
Results:  [[1, 0, 0], [1, 0, 0], [1, 0, 0], [1, 0, 0], [1, 0, 0]]
Result:  [1, 0, 1]
Results:  [[1, 0, 1], [1, 0, 1], [1, 0, 1], [1, 0, 1], [1, 0, 1], [1, 0, 1]]
Result:  [1, 1, 0]
Results:  [[1, 1, 0], [1, 1, 0], [1, 1, 0], [1, 1, 0], [1, 1, 0], [1, 1, 0], [1, 1, 0]]
Result:  [1, 1, 1]
Results:  [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]]

Upvotes: 1

Views: 373

Answers (3)

Eric Duminil
Eric Duminil

Reputation: 54223

What you implement can be described as repeated permutations or cartesian product.

There are k ** length lists or tuples that can be generated this way.

As with any combination, permutation or product, itertools can help you :

from itertools import product

k = 2                  # number of possible values for each element, in this case 0 or 1
length = 3             # length of list

print(list(product(range(k), repeat=length)))
#[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]

Done!

Upvotes: 0

Amal Vincent
Amal Vincent

Reputation: 154

I believe changing results.append(result) to result.append(result[:]) should fix the problem. It is because of the mutability of lists

Upvotes: 0

Moses Koledoye
Moses Koledoye

Reputation: 78546

You are appending the same list everytime. Modifying the list via that reference will propagate changes to every where the list object lives; it is the same list.

You should append a shallow copy instead, so the reference result only modifies the current list:

...
results.append(result[:])

Otherwise, you could create a new list object at the start of the function so each recursive call gets its own list:

def permutations(i, k, length):
    result = []
    ...

Upvotes: 2

Related Questions