从元组列表中获取唯一路径 [英] Getting Unique Paths from list of tuple

问题描述

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

Given a tuple of lists, I need to find all unique path from that:

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,_).

Two tuples can connect if the second element of the tuple matches with the first element of the other tuple i.e: One tuple is (_,a) and other tuple is like (a,_).

最有效的实现方法是什么?我需要找到适合它的最佳数据结构.有什么建议 ?我将在其中执行该算法的元组的数量将超过40万.

What is the most efficient implementation for this ? I need to find the best data structure suited for it. Any suggestions ? The number of tuples in which I will execute the algorithm will be like more than 400,000.

推荐答案

{-# 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 chain generation but I think this problem has exponential time complexity)

已编辑

通常，您必须更精确地定义要返回的路径.

In general, you must to define more preciselly what paths you want to return.

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

Ignoring cycle 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

然后

*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的效率很差，通常，您可以进行许多优化.

uniqTrees has poor efficiency and, in general, you can do many optimizations.

如果要避免循环不变，则可以选择最小的base10表示形式对循环进行归一化，在前面的示例中[[(1,2 ,,(2,3)，(3,1)] == [(2， 3)，(3,1)，(1,3)])1231< 2313然后

If you want to avoid cycle invariant, you can normalize a cycle selecting minimum base10 representation, in 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)]

您可以规范化将其旋转n次并采用"head.sortBy到Base10.旋转"的路径.

you can normalize a path rotating it n-times and taking "head . sortBy toBase10 . rotations".

这篇关于从元组列表中获取唯一路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！