haskell - 从元组列表中获取唯一路径

Question

给定一个列表元组，我需要从中找到所有唯一路径:

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)]]

如果元组的第二个元素与另一个元组的第一个元素匹配，则两个元组可以连接，即:一个元组是 (_,a) ，其他元组类似于 (a ,_)。

最有效的实现是什么？我需要找到最适合它的数据结构。有什么建议 ？我将执行该算法的元组数量将超过 400,000 个。

Answer 1

{-# 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

(您可以优化链生成，但我认为这个问题具有指数时间复杂度)

已编辑

一般来说，您必须更精确地定义要返回的路径。

忽略循环不变式 ([(1,2),(2,3),(3,1)] == [(2,3),(3,1),(1,3)]) 你可以生成所有路径(不使用排列)

{-# 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

然后

*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效率较差，一般来说可以做很多优化。

如果你想避免循环不变，你可以标准化一个循环，选择最小的base10表示，在前面的例子中 ([(1,2),(2,3),(3,1)] == [(2, 3),(3,1),(1,3)]) 1231 < 2313 那么

normalize [(2,3),(3,1),(1,3)] == [(1,2),(2,3),(3,1)]

您可以规范化路径，将其旋转 n 次并采用“head . sortBy toBase10 .rotations”。