Getting unique paths from a list of tuples
Given a set of lists, I need to find all unique paths:
Example I/P: [(1,2),(2,3),(3,4),(9,11),(4,5),(5,6),(6,7),(3,9)]
O/P: [[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)],[(1,2),(2,3),(3,9),(9,11)]]
Two tuples can be connected if the second element of the tuple is the same as the first element of another tuple. i: One tuple (_,a)
and the other tuple is like (a,_)
.
What's the most efficient implementation for this? I need to find the best data structure that suits her. Any suggestions? The number of tuples in which I will execute the algorithm will be more than 400,000.
source to share
{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.List (permutations, nub)
path :: Eq a => [(a, a)] -> [(a, a)]
path [] = []
path [x] = [x]
path (u@(_, a):v@(b, _):xs) = if a == b then u:path (v:xs) else [u]
allPaths = nub . map path . permutations
(you can optimize the generation chain, but I think this problem has exponential time complexity)
EDITED
In general, you should be more specific about which paths you want to return.
Ignoring loop invariant ([(1,2), (2,3), (3,1)] == [(2,3), (3,1), (1,3)]) you can generate all paths (without using permutations)
{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.List (permutations, nub, sortBy, isInfixOf)
data Tree a = Node a [Tree a] deriving Show
treeFromList :: Eq a => a -> [(a, a)] -> Tree a
treeFromList a [] = Node a []
treeFromList a xs = Node a $ map subTree $ filter ((a==).fst) xs
where subTree v@(_, b) = treeFromList b $ filter (v/=) xs
treesFromList :: Eq a => [(a, a)] -> [Tree a]
treesFromList xs = map (flip treeFromList xs) $ nub $ map fst xs ++ map snd xs
treeToList :: Tree a -> [[a]]
treeToList (Node a []) = [[a]]
treeToList (Node a xs) = [a:ws | ws <- concatMap treeToList xs]
treesToList :: [Tree a] -> [[a]]
treesToList = concatMap treeToList
uniqTrees :: Eq a => [[a]] -> [[a]]
uniqTrees = f . reverse . sortBy ((.length).compare.length)
where f [] = []
f (x:xs) = x: filter (not.flip isInfixOf x) (f xs)
allPaths = uniqTrees . treesToList . treesFromList
then
*Main> allPaths [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 1)]
[[2,4,1,2,3,4],[2,3,4,1,2,4],[1,3,4,1,2,4],[1,3,4,1,2,3],[1,2,4,1,3,4],[1,2,3,4,1,3]]
uniqTrees
has low efficiency and, in general, you can do a lot of optimizations.
If you want to avoid the loop invariant, you can normalize the loop by choosing the minimum base10 representation, in the previous example ([(1,2), (2,3), (3,1)] == [(2, 3), ( 3,1), (1,3)]) 1231 <2313, then
normalize [(2,3),(3,1),(1,3)] == [(1,2),(2,3),(3,1)]
you can normalize the path by rotating it n times and taking "head. sortBy toBase10. rotations".
source to share
I think your problem fits the NP category as:
A Hamiltonian path, also called a Hamiltonian path, is a path between two vertices of a graph that visits each vertex exactly once.
In general, the problem of finding a Hamiltonian trajectory is NP-complete (Garey and Johnson 1983, pp. 199-200), so the only known way to determine if a given general Hamiltonian graph has a way to do an exhaustive search ( source )
Your problem is even more "complicated" since you don't know in front of you what the end of the node will be.
In terms of data structure, you can try to model the structure of a hash table in Haskell, since this data type is commonly used in a graph and you can turn the problem into a graph.
source to share