Traveling Salesman

import random
import math
import pprint
from matplotlib import pyplot as plt

def create_nodes(num_nodes, num_rows):
    elements = range(1, num_nodes + 1)
    return [random.sample(elements, num_nodes) for _ in range(num_rows)]

def mutate(table, node_table, mutate_probability, cross_probability):
	for next_id, row in enumerate(table, 1):
		nodes = len(row)
		# print
		# print "Original: ", row
		#mutation
		if random.random() > mutate_probability:
			mini, maxi = sorted(random.sample(range(nodes),2))
			row[mini:maxi+1] = row[mini:maxi+1][::-1]
			# print "After mutation: ", row
			# print "Between: ", mini, maxi

		#crossover
		if random.random() > cross_probability:
			try:
				next_row = table[next_id]
				# print "Parent: ", next_row
			except IndexError:
				pass
			else:
				half_length = nodes//2
				mini = random.randint(0, half_length)
				maxi = mini + half_length - 1 + (nodes % 2)

				crossed = [None] * nodes
				# print "Before crossed: ", row
				crossed[mini:maxi+1] = next_row[mini:maxi+1]
				# print "Cross with: ", crossed
				iterator = 0
				for element in row:
					if element in crossed:
						continue
					while mini <= iterator <= maxi:
						iterator += 1
					crossed[iterator] = element
					iterator += 1
				row[:] = crossed
				# print "After crossed: ", row
				# print "Between: ", mini, maxi
def sample_best(table, node_table):
	t1, t2 = random.sample(table[1:], 2)
	# print "t1: ", t1
	# print "t2: ", t2
	return distance(t1, t2, node_table)

def distance(s1, s2, node_table):
    distance1 = sum_distances(s1, node_table)
    # print "Distance 1: ", distance1
    distance2 = sum_distances(s2, node_table)
    # print "Distance 2: ", distance2

    if distance1 < distance2:
        return s1, distance1
    else:
        return s2, distance2

def sum_distances(strategy, node_table):
    dist = 0
    first_row, second_row = node_table

    for idx_next_node, node1 in enumerate(strategy, 1):
        try:
            node2 = strategy[idx_next_node]
        except IndexError:
            node2 = strategy[0]
        dist += math.hypot(
            first_row[node2-1] - first_row[node1-1],
            second_row[node2-1] - second_row[node1-1])

    return dist

def draw_graph(node_table, strategy):
    graphX = [node_table[0][index - 1] for index in strategy]
    graphY = [node_table[1][index - 1] for index in strategy]

    plt.scatter(graphX, graphY)
    plt.plot(graphX, graphY)
    plt.show()


def main(nodes=8, strategies=6, generations=100, mutateP=.7, crossP=.7):
	#create node locations
	node_table = create_nodes(nodes, 2)
	# for i in range(2):
	# 	print node_table[i]

	#create first generation
	table = create_nodes(nodes, strategies)
	# for i in range(strategies):
	# 	print i
	# 	print table[i]

	print "TOP MEN are looking through:"
	print strategies, "strategies in", generations, "generations with",
	print nodes, "nodes in each strategy..."

	best_score = None
	for count in range(generations):
		mutate(table, node_table, mutateP, crossP)
		# crossover(table, node_table, crossP)
		strategy, score = sample_best(table, node_table)

		if best_score is None or score < best_score:
			best_strategy = strategy
			best_score = score

		if count % 100 == 0:
			print "Foraged", count, "berries"
			print "Best we got so far:", best_score, "with: ", best_strategy


		# if count % 2 == 0:
		# 	print "new table:"
		# 	print count
		# 	for i in range(strategies):
		# 		print table[i]



	print "=========================================================================="
	print "Best we could find: ", best_score, "for strategy", best_strategy

	draw_graph(node_table, best_strategy)

main()