user6851246 user6851246 - 2 months ago 18
Python Question

Global list is appending nothing

answers = []

def search(visit_order, nodes_to_visit, distance):

if len(nodes_to_visit) == 0:
print visit_order
answers.append(visit_order)
return
else:
for node in nodes_to_visit:
nodes_to_visit.remove(node)
visit_order.append(node)
search(visit_order, nodes_to_visit, 0)
visit_order.remove(node)
nodes_to_visit.append(node)

search([],nodes, 0)
print answers


I have a global list
answers
and a recursive function that goes through given
nodes_to_visit
list which will add
visit_order
to the
answers
list when there are no more
nodes_to_visit
.

When I print
Visit_order
right before appending, I get a correct value. However, when I print
answers
, I only get list of lists such as
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
. What is the problem?

For example, if I give search([],[1,2,3,4],0) as the input it is supposed to give me something like
[[3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4], [3, 1, 2, 4]]
but it gives me [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []] instead.

Answer

So the problem is you are appending the same object to answers which you then empty. Check the output of [id(e) for e in answers] and you should see the same object ids. A quick fix is to append a copy by using answers.append(list(visit_order)) or answers.append(visit_order[:])

In [4]: search([],[1,2,3,4],0)

In [5]: answers
Out[5]: 
[[],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]

In [6]: [id(e) for e in answers]
Out[6]: 
[140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400,
 140399731251400]

In [7]:

However, if I change the function to:

def search(visit_order, nodes_to_visit, distance):

    if len(nodes_to_visit) == 0:
        answers.append(visit_order[:])
        return
    else:
        for node in nodes_to_visit:
            nodes_to_visit.remove(node)
            visit_order.append(node)
            search(visit_order, nodes_to_visit, 0)
            visit_order.remove(node)
            nodes_to_visit.append(node)

Now...

In [8]: answers = []

In [9]: search([],[1,2,3,4],0)

In [10]: answers
Out[10]: 
[[1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 3, 4, 2],
 [1, 3, 4, 2],
 [1, 3, 2, 4],
 [1, 3, 2, 4],
 [2, 4, 3, 1],
 [2, 4, 3, 1],
 [2, 3, 1, 4],
 [2, 3, 1, 4],
 [2, 3, 4, 1],
 [2, 3, 4, 1],
 [3, 1, 4, 2],
 [3, 1, 4, 2],
 [3, 4, 2, 1],
 [3, 4, 2, 1],
 [3, 4, 1, 2],
 [3, 4, 1, 2],
 [3, 2, 1, 4],
 [3, 2, 1, 4],
 [3, 1, 4, 2],
 [3, 1, 4, 2],
 [3, 1, 2, 4],
 [3, 1, 2, 4]]

In [11]: