@@ -0,0 +1,1825 @@
+#!/usr/bin/env python3%0A%0Afrom itertools import permutations%0A# TODO rethink if it's better to change tour class to module method creating tuples%0Adists = %5B %5B 10,  0, 1, 2, 3, 4, 5 %5D,%0A          %5B 11,  1, 0, 2, 3, 4, 5 %5D,%0A          %5B 12,  2, 2, 0, 3, 4, 5 %5D,%0A          %5B 13,  3, 3, 3, 0, 4, 5 %5D,%0A          %5B 14,  4, 4, 4, 4, 0, 5 %5D,%0A          %5B 9,   5, 5, 5, 5, 5, 0 %5D,%0A        %5D%0A# One tour cycle object%0Aclass Tour:%0A    def __init__(self, city1,city2,city3):%0A        # find best tour through this three cities%0A        self.tlen = float('+inf')%0A        for c1,c2,c3 in permutations(%5Bcity1,city2,city3%5D):%0A            cur = self.__compute_len__(c1,c2,c3)%0A            if cur %3C self.tlen:%0A                self.tlen = cur%0A                self.c1,self.c2,self.c3 = c1,c2,c3%0A%0A    def cities_list(self):%0A        return %5Bself.c1, self.c2, self.c3%5D%0A    def __compute_len__(self, c1,c2,c3):%0A        return dists%5Bc1%5D%5B0%5D + dists%5Bc1%5D%5Bc2%5D + dists%5Bc2%5D%5Bc3%5D + dists%5Bc3%5D%5B0%5D%0A    def __str__(self):%0A        return str(self.c1) + %22-%3E%22 + str(self.c2) + %22-%3E%22 + str(self.c3) + %22 = %22 + str(self.tlen)%0A    def __cmp__(self, other):%0A        return cmp(self.tlen, other.tlen)%0A%0A# generate all 3-cities tours%0Atours = %5B%5D%0ANCITIES = len(dists)%0Afor i in range(0, NCITIES):%0A    for j in range(i+1, NCITIES):%0A        for k in range(j+1, NCITIES):%0A            tours.append(Tour(i,j,k))%0A# and sort them according to their length%0Atours.sort()%0A# choose best 3-tours%0Ares = %5B%5D%0Avisited = set(%5B%5D)%0Afor t in tours:%0A    if set(t.cities_list())&visited == set(%5B%5D):%0A        for c in t.cities_list():%0A            visited.add(c)%0A        res.append(t.cities_list())%0A# and append the cities that hadn't been choosen%0Aif NCITIES %25 3 != 0:%0A    all_cities = set(range(0, NCITIES))%0A    not_visited = list(all_cities - visited)%0A    res.append(not_visited)%0A# print the result%0Aprint(str(res))%0A

add first version of greedy algorithm