Python Python: Fun problem. Solving Program is Bugged. Why?

[Swimmingly!]

I hope I'm in the right section.
This part is not important but this is thought behind the program.
If you have n-mathematicians and each has a secret number. How many phone calls have to be made for all mathematicians to know all numbers? In this brute force approach I, hypothesize that you need m calls and and try all combinations possible. When it works it'll print 1, if not it prints 0.
D represents what numbers each mathematician knows.
X represents the combination of phone calls chosen.

The bug is this:
D is a list of lists. X is a list.
The function at "def F(D,X):", makes A=D, makes some additions on A (eg: A+=A[j]), and then turns A into a list of sets. [set()...]
The loop at bottom repeats this process for all possible X. But somehow D is changed and turns into a list of sets, and since I can't add sets it stops! But why did D become a list of sets? I never tell D to change in the loop.

m=3
n=3

X=[]
Z=[]
D=[]
for i in range(0,2*m):
	X.append(0)
	Z.append(n-1)	
for i in range(0,n):
	D.append([i])
print 'X,Z,D=',X,Z,D

def F(D,X):
	A=D
	print 'D=',D							#Here for debugging purposes:
	print 'A=',A							#Here for debugging purposes:
	for i in range(0,m):
		A[X[2*i]]+=[X[2*i+1]]
		A[X[2*i+1]]=A[X[2*i]]
	for i in range(0,n):
		A[i]=set(A[i])
	return A

def T(A):
	s=0
	for i in range(0,n-1):
		if A[i]==A[i+1]:
			s+=1
	if s==n-1:
		return 1
	else:
		return 0

i=2*m-1
while X!=Z:
	if X[i]!=n-1:
		if i==2*m-1:
			print T(F(D,X))
		X[i]+=1
		i=2*m-1
	else:
		if i==2*m-1:
			print T(F(D,X))
		X[i]=0
		i-=1

Output:

X,Z,D= [0, 0, 0, 0, 0, 0] [2, 2, 2, 2, 2, 2] [[0], [1], [2]]
D= [[0], [1], [2]]
A= [[0], [1], [2]]
0
D= [set([0]), set([1]), set([2])]
A= [set([0]), set([1]), set([2])]
Traceback (most recent call last):
  File "blahblah.py", line 40, in <module>
    print T(F(D,Z))
  File "blahblah.py", line 19, in F
    A[Z[2*i]]+=[Z[2*i+1]]
TypeError: unsupported operand type(s) for +=: 'set' and 'list'
Press any key to continue . . .

 

[Grep]

This is a common stumbling block. You need to be very clear about the difference between mutable and immutable objects in Python. The problem is, A = D leaves A not as a copy of D, but as a reference to the actual D object. They're now just two ways of referencing the same data.

You'll need to create a new list from the other. Here's a way to do it:

A = list(D)

I strongly suggest you find more materials on how mutable and immutable objects, and references, work in Python. That'll help prevent some serious pain later, trust me. :)

 

[Swimmingly!]

I tried what you said and changed it to:

def F(D,X):
	A=list(D)
	print 'D=',D
	for i in range(0,m):

but the output is:

X,Z,D= [0, 0, 0, 0, 0, 0] [2, 2, 2, 2, 2, 2] [[0], [1], [2]]
D= [[0], [1], [2]]
0
D= [[0, 0, 0, 0], [1], [2]]
0
D= [[0, 0, 0, 0, 0, 0, 1], [1], [2]]
0
D= [[0, 0, 0, 0, 0, 0, 1, 0, 0, 2], [1], [2]]
0

ie D is still changing. ie A is still a "reference to D".
I will however read about these "mutable and immutable objects and references". I learned python through copying and testing so sometimes I end up being ignorant about these things. Thanks a lot for giving me a lead on the problem.

Edit: BOTH the codes are INCOMPLETE. I don't need to post it all. I posted what matters.

 

[Grep]

ie D is still changing. ie A is still a "reference to D".
I will however read about these "mutable and immutable objects and references". I learned python through copying and testing so sometimes I end up being ignorant about these things. Thanks a lot for giving me a lead on the problem.

Ah, I haven't had time to go through your code in great detail, but remember that the method I gave you makes a "shallow copy" of the list, and any mutable objects in that list will still be the original references from the original list. That is, a list of lists, copied in this way, will be a new list containing the lists that were contained in the original one.

By the way, another method of making a shallow copy, for future reference, is A = D[:].

Anyways, try a deep copy using the copy module, which will make full copy of everything:

import copy

A = copy.deepcopy(D)

I'll check back in tomorrow in case you're still stuck. Good luck, and you're welcome! :)