查找两个列表的所有可能交集

Question

假设我有一个列表 [2,4,1,5,4] 和一个列表 [2,4,5,1] 然后我希望有一个相交函数，它会给我所有可能的交集。因此，在这种情况下，该函数将输出 [[2,4,1,5], [2,1,5,4]] 的列表。

内置相交会给我 [4,2,1,5,4]。

我试着从创建一个函数开始

intersect' xs ys = xs \ (xs \ ys)

这只给了我一种可能性 - [2,1,5,4]。

如有任何帮助，我将不胜感激。

Answer 1

The built in intersect will give me [4,2,1,5,4].

并且从 [4,2,1,5,4] 你可以使用这个函数得到 [[2,4,1,5], [2,1,5,4]]:

uniqs :: Eq a => [a] -> [[a]]
uniqs  []    = [[]]
uniqs (x:xs)
    | x `elem` xs = map (x:) (uniqs (filter (/= x) xs)) ++ uniqs xs
    | otherwise   = map (x:) (uniqs xs)

那么你的intersections就是

intersections :: Eq a => [a] -> [a] -> [[a]]
intersections xs ys = uniqs (intersect xs ys)

Answer 2

由于您将第二个列表用作多集，因此让我们在类型中明确说明：

intersections :: Ord a => [a] -> MultiSet a -> [[a]]

列表和空多重集的唯一交集是空列表

intersections _ m | M.null m = [[]]

空列表和非空多集没有交集

intersections [] _ = []

给定一个非空列表和一个非空多重集，我们有所有使用第一项的交集，以及所有不使用第一项的交集

intersections (a:as) m = with ++ without

如果列表中的第一项不在多重集中，则没有使用它的交集

  where with = case M.lookup a m of
          Nothing -> []

如果它在多集中，那么使用该项目的交集只是列表其余部分与删除该项目的一个实例后的多集的交集的扩展，

          Just n -> map (a:) . intersections as $ update a (n-1) m

不使用item的交集很容易通过递归定义

        without = intersections as m

为了完整起见，多集的定义：

import qualified Data.Map as M
import qualified Data.List as L

type MultiSet a = M.Map a Int

fromList :: Ord a => [a] -> MultiSet a
fromList = L.foldl' (\m a -> M.insertWith' (+) a 1 m) M.empty

toList :: MultiSet a -> [a]
toList = concatMap (uncurry $ flip replicate) . M.toList

update :: Ord a => a -> Int -> MultiSet a -> MultiSet a
update a 0 = M.delete a
update a n = M.insert a n

查找两个列表的所有可能交集

Finding all possible intersections of two lists

list

haskell

intersection