import random

x = [] 
Y = []
Z = []
n=3
total = 36;
size = 4;
target = total/size
partitions = [];

def fixPartition(Ss, target):
	Ts = []
	for s in Ss:
		m = min(s)
		if m < 0:
			t = set(a - m for a in s) 
			target -= m
		else:
			t = s
		Ts.append(t)
	return (Ts, target)

def randomPartition(size, target):
	while True:
		X = set()
		Y = set()
		Z = set()
		while max(len(X), len(Y), len(Z)) < size:
			x = random.randint(0, target//4*3);
			y = random.randint(0, target//4*3);
			z = target - x - y
			X.add(x)
			Y.add(y)
			Z.add(z)

		A = None
		if len(X) < size:
			if len(Y) < size:
				if len(Z) < size:
					pass
				else:
					A = X
					B = Y
			else:
				if len(Z) < size:
					A = X
					B = Z
				else:
					B = X
		else:
			if len(Y) < size:
				if len(Z) < size:
					A = Y
					B = Z
				else:
					B = Y
			else:
				if len(Z) < size:
					B = Z
				else:
					continue

		if A != None:
			while len(A) < size:
				a = random.randint(0, target//4*3)
				A.add(a)
		
		while len(B) < size - 2:
			b = random.randint(0, target)
			B.add(b)
		m = size * target - sum(X) + sum(Y) + sum(Z)
		
		for c in range(m//2, target*2):
			if c not in B and m - c not in B:
				B.add(c)
				B.add(m-c)

				yield fixPartition([X, Y, Z], target)
				break
		continue
		
	
def altePartition(sum, largestNumber, way):
	#print way
#	print "%d\t%d\t" %(sum, largestNumber)
	depth = len(way)
	if (largestNumber ==0):
		return 0;
	if (sum==0):
		if (depth == size*3):
			partitions.append(way)
		return 1;	
	if (sum < 0):
		return 0;
#	if(depth >=size*3):
#		return 0;
	way1 = way[:]
	way.append(largestNumber);
	way2=way;
	return partition(sum, largestNumber -1, way1) + partition(sum - largestNumber,largestNumber, way2);

		
def randomInstance():
	n = random.randint(0, len(partitions) -1);
	return random.sample(partitions[n], len(partitions[n]))
def edges(X,Y,Z):
	return [[x,y,z] for x in X for y in Y for z in Z if x + y + z == target]
	
	#edges = []
	#for x in X:
	#	for y in Y:
	#		for z in Z:
	#			if (x + y + z == target):
	#					edges.append([x,y,z])
	#return edges;

def basicCheck(X, Y, Z, edges):
	if (len(edges) < size*3):
		print("size wrong")
		return False;
	index = range(0, len(edges))
	for x in X:
		check = False
		for i in index:
			if (x == edges[i][0]):
				check = True;
				index.remove(i);
				break;
		if (not check):
			return False;
	index = range(0, len(edges))
	for y in Y:
		check = False;
		for i in index:
			if (y == edges[i][1]):
				check = True;
				index.remove(i);
				break;
		if (not check):
			return False;

	index = range(0,len(edges))
	for z in Z:
		check = False;
		for i in index:
			if (z == edges[i][2]):
				check = True;
				break;
		if (not check):
			return False;

		
	return True

def hasMatching(X, Y, Z,target):
	if len(X) == 0:
		return True
	x = next(iter(X))
	for y in Y:
		z = target - x - y
		if z in Z:
			XX = X.copy(); XX.remove(x);
			YY = Y.copy(); YY.remove(y);
			ZZ = Z.copy(); ZZ.remove(z);
			if hasMatching(XX, YY, ZZ, target):
				return True
	return False

def specialInstance(X, Y, Z, target):
	XYZ = set()
	XYZ.update(X)
	XYZ.update(y + 3 * target for y in Y)	
	XYZ.update(z + 6 * target for z in Z)	
	return ([XYZ, XYZ, XYZ], 10*target)

def divide(S):
	X = S[:size];
	Y = S[size: 2*size];
	Z = S[2*size:];
	return [X,Y,Z]

def test(size, wanted):
	i = 0
	j = 0
	for [X, Y, Z], target in randomPartition(size, wanted):
		i += 1
		if hasMatching(X, Y, Z, target):
			continue
		j += 1
		[Xs, Ys, Zs], ts = specialInstance(X, Y, Z, target)	
		if hasMatching(Xs, Ys, Zs, ts):
			print(Xs, Ys, Zs, ts)
			break
		print (i, j, i-j)

def main():
	pass

def m():
	way=[]
	partition(total, target -1, way);
	instance = randomInstance();
	print instance
	sets = divide(instance);
	print sets;
	X = sets[0];
	Y = sets[1];
	Z = sets[2]
	edgeSet= edges(X,Y,Z)
	print basicCheck(X,Y,Z, edgeSet)
	S = [3,3,3,3]
	es = edges(S,S,S)
	print basicCheck(S,S,S,es)
	print instance
	print sets
	print edgeSet

if __name__ == "__main__":
	main()