Permutation implementation-CodePudding

permutation_str works fine but permutation_arr doesn't output the correct answer. I don't see why the two functions are generating different outputs given the fact that they have the same implementation. Is there something that I'm missing?

def permutation_arr(res, arr):
    if len(arr) == 0:
        print(res)
    
    for i in range(len(arr)):
        res.append(arr[i])
        permutation_arr(res, arr[:i]   arr[i 1:])
        res = res[:-1]

permutation_arr([], [1,2,3])

def permutation_str(res, str):
    if len(str) == 0:
        print(res)
    
    for i in range(len(str)):
        res = res   str[i]
        permutation_str(res, str[:i]   str[i 1:])
        res = res[:-1]

permutation_str("", "123")

CodePudding user response：

arrays are mutable... so that res you keep appending is always the same

try this instead

def permutation_arr(res, arr):
    if len(arr) == 0:
        print(res)
    
    for i in range(len(arr)):
        res.append(arr[i])
        # send a copy of res instead of res
        permutation_arr(res[:], arr[:i]   arr[i 1:])
        res = res[:-1]

permutation_arr([], [1,2,3])

CodePudding user response：

The right way to do is remove the last element using pop after you are done with a recursive call. Don't create a copy again. pop won't throw an empty list exception because you are doing it after append. The res[:-1] creates a different list and you don't want to change the list when passing along in your recursive calls, you'd want the same list to be passed all along the recursion.

def permutation_arr(res, arr):
    if len(arr) == 0:
        print(res)
    
    for i in range(len(arr)):
        res.append(arr[i])
        permutation_arr(res, arr[:i]   arr[i 1:])
        res.pop()

permutation_arr([], [1,2,3])

output:

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