Haskell：兩個整數列表之間的匹配數目？

說我有一個整數兩個列表：Haskell：兩個整數列表之間的匹配數目？

4 12 24 26 35 41 

42 24 4 36 2 26

有兩個列表之間的3場比賽。

如何計算匹配任何兩個列表在Haskell之間有多少？

謝謝。

來源

2011-12-15 Griffin

如果`2`在第二個名單是另一個`4`，會做4場比賽嗎？如果第一個列表中的'12'也是另一個'4'，那麼是否會進行6場比賽，4場比賽，還是隻有3場比賽？ – dave4420 2011-12-15 11:13:45

對不起，我應該更清楚，列表不包含任何重複。我現在得到了我的答案，謝謝。 – Griffin 2011-12-15 11:15:15

如果您不需要照顧多個元素的，簡單的方法是計算交叉口

import Data.List 

matches :: Eq a => [a] -> [a] -> Int 
matches xs ys = length (intersect xs ys)

某種程度上更高效的長度是用Set S作爲中間結構，如果你也有一個Ord實例：

import qualified Data.Set as S 

matches :: Ord a => [a] -> [a] -> Int 
matches xs ys = S.size (S.intersection (S.fromList xs) (S.fromList ys))

如果你需要重複的護理，使用Map計數出現的每個元素的數量將是一個不太難的修改。

來源

2011-12-15 11:07:08

設置好的演示; Haskellers確實應該嘗試更頻繁地使用List之外的適當容器。 – 2011-12-15 21:12:57

這將與清單相當痛苦的你會需要通過他們所有對去。像這樣的東西打印出正確的答案，形成所有對他們是平等的，然後計算大小。

let xs = [1,2,3,4] 
let ys = [1,2,3,4] 
length [x | x <- xs, y <- ys, x == y]

從性能的角度來看，這樣做很尷尬。對於大的列表，你最好使用一組，你可以測試會員更快（通常是O（LG N），有時O（1））比你可以用列表（O（N））。

來源

2011-12-15 11:00:48

感謝您的回答。 – Griffin 2011-12-15 11:15:43

從Data.List函數intersect返回兩個給定的列表之間的交叉點。

import Data.List (intersect) 

numberOfIntersections :: (Eq a) => [a] -> [a] -> Int 
numberOfIntersections xs ys = length $ intersect xs ys 

main = do 
    print $ numberOfIntersections [4, 12, 24, 26, 35, 41] [42, 24, 4, 36, 2, 26]

來源

2011-12-15 11:08:13 drmegahertz

如果你想只使用列表的解決方案，這是不一樣Data.List.intersect這麼慢，你可以使用這個：

intersectSorted [] _ = [] 
intersectSorted _ [] = [] 
intersectSorted (x : xs) (y : ys) = case compare x y of 
    LT -> intersectSorted xs (y : ys) 
    EQ -> x : intersectSorted xs ys 
    GT -> intersectSorted (x : xs) ys 

intersect a b = intersectSorted (sort a) (sort b)

來源

2011-12-15 22:06:08 Rotsor

Haskell：兩個整數列表之間的匹配數目？

回答

相關問題