import random

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

def partition(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):
	if len(X) == 0:
		return True
	x = next(iter(X))
	for y in Y:
		if target - x - y in Z:
			if hasMatching(X - set(x), Y -set(y), Z- set(target - x - y)):
				return True
	return False

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

def main():
	partition(total, target - 1, way);
	for p in partitions:
		
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()