Python: weird behavior of list append function

Question

I'm a newbie in Python.

I try to make a Kruskal algo. Here is my code:

#c={('v','a'):5,('v','g'):5,('g','a'):5,('v','b'):7,('v','e'):4,('f','e'):8,('f','b'):8,('f','c'):11,('c','e'):9,('c','d'):7,('c','b'):9,('e','d'):8}
#n=8

def argmin(c):
    m=1e100
    r=()
    for i in c:
       if c[i]<m:
           m=c[i]
           r=i
    return r

def kruskal (n, c):
    T=[]
    B=[]
    while len(T)<n-1:
        E=argmin(c)
        c.pop(E)
        e=[]
        e+=E
        a0=0
        a1=0
        f0=-1
        f1=-1
        cross=0
#        print('e avant',e)
        for i in range(len(B)):
            for j in range(len(B[i])):
                if e[0]==B[i][j]:
                    cross+=1
                    f0=i   
                if e[1]==B[i][j]:
                    cross+=1
                    f1=i                        
            if cross==2: break
            else: cross=0
        if cross==2: continue
#        print('e apres',e)
        T.append(e)
#        print('T',T)
        if f0!=-1 and f1!=-1:
            B[f0].extend(B[f1])
            B.pop(f1)
        elif f0!=-1:
            B[f0].extend(e[1])
        elif f1!=-1:
            B[f1].extend(e[0])
        else :
            B.append(e)        
#        print('B', B)                
    return T

The problem I have is in the line where is: "T.append(e)" In the result T[0] is not what I expect. if I input the following:

c={('v','a'):5,('v','g'):5,('g','a'):5,('v','b'):7,('v','e'):4,('f','e'):8,('f','b'):8,('f','c'):11,('c','e'):9,('c','d'):7,('c','b'):9,('e','d'):8}

n=8

Then I call my function: kruskal(8, c) I get:

[['v', 'e', 'g', 'a', 'b', 'f', 'c', 'd'], ['v', 'g'], ['v', 'a'], ['v', 'b'], ['c', 'd'], ['f', 'b'], ['e', 'd']]

Where as I expect the following:

[['v', 'e'], ['v', 'g'], ['v', 'a'], ['v', 'b'], ['c', 'd'], ['f', 'b'], ['e', 'd']]

in an iteration I have this: T= [['v', 'e'], ['g', 'a'], ['v', 'a']] e= ['v', 'b'] Then after a "T.append(e)", I get: T= [['v', 'e', 'g', 'a'], ['g', 'a'], ['v', 'a'], ['v', 'b']] So what's wrong here sirs. — EL FARAH, Mar 25 '15 at 07:55
Check the part where you do `e += E`, in this chunk, you have `e` which is a list and `E` which is a tuple, so it extends `e` with the elements of `E`. You may want to use `append` if `e` is supposed to be growing over iteration, or empty `e` at the beginning of the iteration. — Benoît Latinier, Mar 25 '15 at 08:04
Try it with a small amount of data, one value for example, or even none. See what happens. — Peter Wood, Mar 25 '15 at 08:05
I still don't get it! yes I'm converting E the tuple into e the list. e is emptied when I had e=[]. Why in an iteration T.append(e) e get appended both to the end of T and to T[0] too???!! — EL FARAH, Mar 25 '15 at 08:11
Please uncomment the "print" and try the code with inputs provided. — EL FARAH, Mar 25 '15 at 08:13

itzMEonTV · Answer 1 · 2015-03-25T08:51:58.600

Not looking for all your code.But something is found that, You are appending references of list sometime.So to simply fix:

from copy import deepcopy

T.append(deepcopy(e)) #in place of T.append(e)

Will give output as

[['v', 'e'], ['g', 'a'], ['v', 'a'], ['v', 'b'], ['c', 'd'], ['f', 'b'], ['e', 'd']]

Example

a = [1, 2]
b = a
b.append(3)

>>>a
[1,2,3]

>>>b
[1,2,3]

What is happening here

a = [1,2]
b = a

>>>id(a), id(b)
(140526873334272, 140526873334272)

That is list [1,2] is tagged by two variables a and b. So any changes to list will affect every varables tagged to it.

score 0 · Answer 2 · edited May 23 '17 at 12:21

The answer by itzmeontv is correct regarding the underlying reason for your problem the first member of T is a mutable list, which you then modify further on in your code. The code path why this happens in your case is a little complicated:

On the first iteration through your algorithm, you append e to T - so T[0] refers to the list name e at that point (contents ['v','e'])
On that same iteration, you always hit this block:
```
 else :
     B.append(e)
```
This means that B[0] now refers to the list named e as well - i.e. T[0] refers to the same list as that in B[0] and any changes to B[0] will be reflected in T[0] as lists are mutable.
The next iteration then creates a new e - but the list referred to in B[0] and T[0] is still that same list i.e. ['v','e']
You then continue to extend this list when you do B[f0].extend(B[f1]) in the cases where f0 is zero

This is a symptom of assigning a list not making a copy in Python, a detailed treatment of which is given in this question if you want to deepen your understanding. A range of options of how to append your list to T is given along with timings - you might, for instance, like to write T.append(e[:]), with the slice notation implicitly making a copy of e at the point you append it.

One thing you might want to consider is whether you need the members of T to be mutable once they are added to T. If you do not - an option may be to append tuples rather than lists - i.e.

T.append(tuple(e))

Python: weird behavior of list append function

2 Answers2