Haskell:查找等于 n 的元素元组

Question

我正在尝试在 Haskell 中编写一个函数，该函数接受整数列表和整数 n 并查找等于 n 的所有元组。到目前为止，我已经有了一个有效的实现

tuplesum :: (Eq b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = [(x1,x2) | x1 <- xs, x2 <- xs, x1 + x2 == n, x1 <= x2]

所以如果我给这个函数输入

tuplesum [5,1,4,0,5,6,9] 10

输出是 [(5,5),(5,5),(1,9),(4,6),(5,5),(5,5)]但是，我有 4 个 (5,5) 解决方案的重复项。我希望该函数输出 [(5,5),(1,9),(4,6)] 但我无法弄清楚如何约束具有相同整数的元组而不删除它完全作为一个解决方案。

Answer 1

元组生成中的对称性破缺

我的印象是，您正在寻找一种从列表中选择两个元素的方法，以便 x1 始终位于之前 x2.

始终让 x2 迭代列表其余部分的常见方法是使用 tails :: [a] -> [[a]] 。对于列表，tails 将生成列表的所有尾部的列表，从列表本身开始。例如:

Prelude Data.List> tails [1, 4, 2, 5]
[[1,4,2,5],[4,2,5],[2,5],[5],[]]

我们可以将其与模式匹配一​​起使用来选择一个元素，并获取对剩余元素的引用。例如:

import Data.List(tails)

tuplesum :: (Eq b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = [(x1,x2) | (x1:x2s) <- tails xs, x2 <- x2s, x1 + x2 == n]

请注意，仍然可以在此处获取重复项，例如，如果 5 在列表中出现三次，因为在这种情况下 x1 可以选择第一个 5，然后x2可以选择第二个5以及最后一个。我们可以利用像 nub :: Eq a => [a] -> [a] 这样的唯一性过滤器为此:

import Data.List(nub, tails)

tuplesum :: (Eq b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = nub [(x1,x2) | (x1:x2s) <- tails xs, x2 <- x2s, x1 + x2 == n]

请注意，这里最好使用 tails，因为它会提高性能，因为我们首先会生成少量的重复项。

使用哈希集获取“其他”元素

上面的算法仍然是O(n²)，而且速度不是很快。然而，我们可以用相反的方式解决问题:我们可以首先构造一个元素的 HashSet，然后对于每个元素 x1，检查是否 n - x1 是一个成员，例如:

import Data.Hashable(Hashable)
import Data.HashSet(fromList, member)

tuplesum :: (Ord b, Hashable b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = nub [(x1,x2) | x1 <- xs, let x2 = n-x1, x1 <= x2, member x2 hs]
    where hs = fromList xs

但是由于nub，运行时间仍然是O(n²)，但是我们可以使用hashNub :: (Eq a, Hashable a) => [a] -> [a]这里:

hashNub :: (Eq a, Hashable a) => [a] -> [a]
hashNub = go HashSet.empty
  where
    go _ []     = []
    go s (x:xs) =
      if x `HashSet.member` s
      then go s xs
      else x : go (HashSet.insert x s) xs

然后让它与:

import Data.Hashable(Hashable)
import Data.HashSet(fromList, member)

tuplesum :: (Ord b, Hashable b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = hashNub [(x1,x2) | x1 <- xs, let x2 = n-x1, x1 <= x2, member x2 hs]
    where hs = fromList xs

现在它的工作时间为O(n log n)。