+import GTA.Data.JoinList;

+import qualified Data.IntSet as IntSet

+import System.Environment

+-- checks whether a given list of edges is a path or not

+isPath = ok <.> homJ' times single nil where

+ ok = maybe False (\_ -> True)

+ single (x, _) = Just $ Just x

+ times Nothing _ = Nothing

+ times _ Nothing = Nothing

+ times (Just Nothing) x = x

+ times x (Just Nothing) = x

+ times (Just (Just (u, v))) (Just ( Just (w, z)))

+ = if v == w then Just $ Just (u, z)

+-- checks whether a given list of edges is a simple cycle of length n or not

+spans n = ok <.> homJ' times single nil where

+ ok x = IntSet.size x == n

+ single ((v,_), _) = IntSet.singleton v

+-- generates a list of edges from 1 to 1 including non-simple cycles.

+genEdgeList n = assignsBy (edges n) [1..n]

+edges n m | m == 1 = [(1, k) | k <- [2..n]]

+ | m == n = [(k, 1) | k <- [2..n]]

+ | True = [(k, l) | k <- [2..n], l <- [2..n], not (k==l)]

+tsp dist n = genEdgeList n

+ `aggregateBy` maxsumsolutionWith (revOrd . dist . fst)

+-- The answer is 1 -> 2 -> ... -> n -> 1 (and its reverse)

+lineardist (m, n) | m == n - 1 = 1

+-- TSP solver (parallel version)

+tspP dist n = assignsByP (edges n) [1..n]

+ `aggregateBy` maxsumsolutionWith (revOrd . dist . fst)

+ let n | length a > 0 = read $ head a

+ putStrLn $ "n = " ++ show n

+ print $ tsp lineardist n

+ghc -threaded -rtsopts TSP.hs -o TSP -O2

+The size of the range of foldr of isPath is n^2+2.

+The size of the range of foldr of spans n is 2^n

+Therefore, the size of a table is O(n^2 2^n) .

+In total, O(n^5 4^n) algorithm.