count variable is not updating in recursive function call

Question

The following code is finding permutation, but the count variable is not updating. Can anyone please point out the mistake as to why the change in count is not reflected.

def swap_arr_elems(arr, src_idx, dest_idx):
    tmp = arr[src_idx]
    arr[src_idx] = arr[dest_idx]
    arr[dest_idx] = tmp
    return

def permuate(arr, left, right, output, count):
    if left == right:
        output.append(list(arr))
        count += 1
        #count.append('1')
        return

    for i in range(left, right, 1):
        swap_arr_elems(arr, left, i)
        permuate(arr, left + 1, right, output, count)
        swap_arr_elems(arr, left, i)


if __name__ == '__main__':
    count = 0    
    #count = []
    test_input = ['a', 'b', 'c']
    test_output = []
    permuate(test_input, 0, len(test_input), test_output, count)
    print("count : " + str(count))
    for item in test_output:
        print(item)

EDIT 1:

output of the above code is:
count : 0
['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['b', 'c', 'a']
['c', 'b', 'a']
['c', 'a', 'b']

Answer 1

You are only increasing the count when left==right and then you are returning from it, increasing count there would not automatically increase it in the calling function, you can try returning the count and then accepting it in the function where it is called.

Example -

def permuate(arr, left, right, output, count):
    if left == right:
        output.append(list(arr))
        count += 1
        #count.append('1')
        return count

    for i in range(left, right, 1):
        swap_arr_elems(arr, left, i)
        count += permuate(arr, left + 1, right, output, count)
        swap_arr_elems(arr, left, i)
    return count

if __name__ == '__main__':
    count = 0    
    #count = []
    test_input = ['a', 'b', 'c']
    test_output = []
    count = permuate(test_input, 0, len(test_input), test_output, count)
    print("count : " + str(count))
    for item in test_output:
        print(item)

Answer 2

I personally name this the mutable and non-mutable effect don't know it's real name

Count is an integer. That is it is an immutable object and it's scope is within the main function so it's value is not changed

That is when you do count+=1 a new object is created and that object is not returned

test_output is an List.This is a mutable object .Even though you change it's value it is changed in the same list

output.append(list(arr)) #adds to the same  test_output list

See this link for more insights on mutable and non-mutable objects and behaviors

As per @brunodesthuilliers output=output+list(arr) changes the output .This is due to the fact + creates a new object see below for explanation

>>> out=[1,2,3]
>>> id(out)
33535760
>>> out.append(2)
>>> id(out)
33535760
>>> out=out+[3]
>>> id(out)
33535600

Answer 3

yes, scope of count variable is only in main loop.

count variable in if main loop and count variable in permuate function are different.

If you want value of count variable from permuate function then return count value from function and accept in count variable.

Demo:

>>> count = 10
>>> def test(count):
...    count += 1
...    print "In test:", id(count)
...    return count
... 
>>> count = test(count)
In test: 149784632
>>> count 
11

Answer 4

permuate function is not returning any value. It is just returning the flow of control the way you wrote it. So, you must modify it to return count. Also, your swap_arr_elems function is not doing anything really because it is not returning any value. Alternatively, you could define variable count in permuate as global.

Answer 5

Primitives are immutable. When you try to increment count inside your function you are switching what memory address count inside the function is referring to, the outside count is unchanged:

In CPython as an implementation detail, the id of an object is also the memory address so we can clearly see this happening:

def fn(inside_count):
    print id(inside_count), '- inside_count before increment' 
    inside_count += 1
    print id(inside_count), '- inside_count after increment'

outside_count = 1
​
print id(outside_count), '- outside_count before fn call'
fn(outside_count)
print id(outside_count), '- outside_count after fn call'

---

140536048575784 - outside_count before fn call
140536048575784 - inside_count before increment
140536048575760 - inside_count after increment
140536048575784 - outside_count after fn call 

---

The behavior of the list object is different because you calling the append function on the object. The memory address referred to by the inside_output doesn't change, the object at the memory address is changed.

def fn(inside_output):
    print id(inside_output), '- inside_output before append' 
    inside_output.append('1')
    print id(inside_output), '- inside_output after append'

outside_output = []
​
print id(outside_output), '- outside_output before fn call'
fn(outside_output)
print id(outside_output), '- outside_output after fn call'

---

4389007440 - outside_output before fn call
4389007440 - inside_output before append
4389007440 - inside_output after append
4389007440 - outside_output after fn call

---

That being said, since you have your permutations in a list, you should just be doing:

print("count : " + str(len(test_output)))