path_counting.py

from itertools import permutations
n = 4
nodes = [i for i in range(n*n)]
edges = []
for i in nodes:
	if i+1 in nodes and (i+1) % n  !=0:
		edges.append((i, i+1))
	if i+n in nodes:
		edges.append((i, i+n))
edges = set(edges)
print(nodes)
print(edges)

#T = [0,int((n*n-1)/2),n*n-1]
T = [0,n*n-1]
print(T)




for t in T:
	nodes.remove(t)
length = 0
path_count = dict()
while length < len(edges):
	path_count[length] = 0
	perms = []
	print("Length = {}".format(length))
	counter = 0
	paths = []
	for p in permutations(nodes, length):
		counter +=1
		paths.append(p)
		for t1 in T:
			for t2 in T:
				if t1<=t2:
					continue
				perm = [t1]+list(p)+[t2]
				valid = True
				# if (t1,t2) == (0,4):
				# 	print(perm)
				#perm = [0,1,4]
				for i  in range(len(perm)-1):
					if not ((perm[i],perm[i+1]) in edges or (perm[i+1],perm[i]) in edges):
						#print(perm[i],perm[i+1])
						# if sorted([t1,t2]) == [0,4]:
						# 	print(perm[i], perm[i+1])
						valid = False
						break
				if valid:
					if perm[0] > perm[-1]:
						perm = perm[::-1]
					print("Valid", perm)
					path_count[length]+=1
				if counter % 1000000 == 0:
					print("Completed", counter)
				paths.append(p)
	print("Found {} paths of length {}".format(path_count[length],length))
	length+=1
for length in path_count:
	if path_count[length]:
		print("Found {} paths of length {}".format(path_count[length],length))