Самый эффективный способ создания Data.Set всех пар элементов в наборе?

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

Каким вычислительно наиболее эффективным способом генерации множества всех неупорядоченных пар элементов является данное множество? * 1012 Т.е. *

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

Итак, вот первый удар по решению с использованием преобразования назад и вперед в список. Опять же, я не уверен, что это самый быстрый способ сделать это, но я знаю, что итерация по наборам не очень эффективна.

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

Складывая молнию поверх хвостов, вы получаете хороший и эффективный способ создания набора неупорядоченных пар. Тем не менее, инстинкт вдохновляет меня на то, что может быть решение monadic filterM или foldM, которое еще более элегантно. Я буду продолжать думать.

[EDIT]

Итак, вот что должно быть [но не из-за размера блока питания] более быстрое решение, которое не требует ToList.

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

Использует решение для набора мощности по монадическим спискам, чтобы построить блок питания, а затем отфильтровать пары. Я могу вдаваться в подробности, если это необходимо.

Answer 3

Сначала вам нужно сгенерировать все наборы. replicateM из Control.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.

Это то, что вы хотите?

UPD

Понимание списка может быть более понятной и быстрой техникой для создания таких подсписков, поэтому вот еще один пример pairs:

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