最有效的创建数据的方法.集合中所有元素对的集合

Question

给定一个包含任意数量的任意类型元素的任意集合，例如

mySet1 = Set.fromList [1,2,3,4]

或

mySet2 = Set.fromList ["a","b","c","d"]

或

mySet3 = Set.fromList [A, B, C, D]

用于某些数据构造函数A, B, C, D，…

生成给定集合中所有无序元素对的集合的最有效计算方法是什么?例如

setPairs mySet1 == Set.fromList [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

或

setPairs mySet2 == fromList [ ("a","b")
                            , ("a","c")
                            , ("a","d")
                            , ("b","c")
                            , ("b","d")
                            , ("c","d") ]

或

setPairs mySet2 == fromList [ (A,B)
                            , (A,C)
                            , (A,D)
                            , (B,C)
                            , (B,D)
                            , (C,D) ]

---

我最初天真的猜测是:

setPairs s = fst $ Set.fold
    (e (pairAcc, elementsLeft) ->
        ( Set.fold
              (e2 pairAcc2 ->
                  Set.insert (e2, e) pairAcc2
              ) pairAcc $ Set.delete e elementsLeft
        , Set.delete e elementsLeft )
    ) (Set.empty, s) s

但这肯定不是最好的解决方案吗?

Answer 1

基准测试可能会证明我错了，但我怀疑停留在集合表示中是没有胜算的。不管怎样，你都需要O(n^2)因为这就是输出的大小。关键的优势在于生成列表时，您可以使用对S.fromDistinctAscList的调用，这样构建集合本身只需要花费O(n)。

下面的代码非常简洁，保留了相当多的共享，而且通常是我能想到的最简单、最直接、最直观的解决方案。

pairs s = S.fromDistinctAscList . concat $ zipWith zip (map (cycle . take 1) ts) (drop 1 ts)
   where ts = tails $ S.toList s

---

编辑

更短/更清晰(不确定性能方面，但可能同样好/更好):

pairs s = S.fromDistinctAscList [(x,y) | (x:xt) <- tails (S.toList s), y <- xt]

Answer 2

首先，需要生成所有集合。控制中心的replicateM。Monad可以帮你。

λ> replicateM 2 [1..4]
[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]

然后需要筛选对，其中第二个元素大于第一个

λ> filter ([x,y] -> x < y)  $ replicateM 2 [1 .. 4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

最后，需要转换元组

中的每个列表

λ> map ([x,y] -> (x,y)) $ filter ([x,y] -> x < y)  $ replicateM 2 [1 .. 4]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

我们可以将其化为函数pairs:

import Data.Set
import Control.Monad
import Data.List
mySet = Data.Set.fromList [1,2,3,4]
--setOfPairs = Data.Set.fromList [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
setOfPairs = Data.Set.fromList $ pairs mySet
pairs :: Ord a => Set a -> [(a,a)]
pairs x = Data.List.map ([x,y] -> (x,y)) $ Data.List.filter ([x,y] -> x < y) $ replicateM 2 $ toList x

所以，如果我对你的问题，你可以使用pairs mySet，其中成对生成mySet的所有无序对的列表。

是你想要的吗?

乌利希期刊指南:

列表理解可能是创建此类子列表的更清晰、更快速的技术，下面是pairs的另一个实例:

pairs :: Ord a => Set a -> [(a,a)]
pairs set = [(x,y) | let list = toList set, x <- list, y <- list, x < y]

Answer 3

这是第一个尝试使用来回转换到列表的解决方案。同样，我不确定这是最快的方法但我知道遍历集合并不是很有效。

import Data.List
import qualified Data.Set as S
pairs :: S.Set String -> S.Set (String,String)
pairs s = S.fromList $ foldl' (st e -> (zip l e) ++ st) [] ls
          where (l:ls) = tails $ S.toList s

通过折叠拉链的尾部，你得到一个很好的和有效的方法来创建一组无序的对。然而，直觉告诉我，也许有一个单元化的filterM或foldM解决方案会更加优雅。我会继续思考的。

[编辑]

所以这里应该是[但不是因为powerset的大小]一个不需要tollist的更快的解决方案。

import Data.List
import qualified Data.Set as S
import qualified Data.Foldable as F
pairs :: (Ord a) => S.Set a -> S.Set (a,a)
pairs s = S.fromList $ foldl two [] $ F.foldlM (st e -> [[e]++st,st]) [] s
          where two st (x:xa:[]) = (x,xa) : st
                two st _ = st

在一元列表上使用幂集解来构建幂集，然后过滤掉幂集对。如果有必要，我可以更详细地说明。