列表中的数字乘数

Question

如何在合并的排序列表中打印给定数字列表的倍数？

即

take 10 (multiples [4,5])

给

4,5,8,10,12,15,16,20,24,25

我已经让它适用于大小为2或1的列表,但我需要一个更通用的解决方案:)

Answer 1

这里有两个有效的解决方案,可以生成排序的无限列表,无需重复,您可以take从中获取.假设您的输入multiples有n个元素.

每个元素O(n)

首先,对于输入中的每个数字,创建其倍数的无限列表.然后,仔细合并这些列表,保持它们的排序并避免重复.(这是问题的难点.)

multiples xs = merge [map (*x) [1..] | x<-xs]

merge xss
    | all null xss = []
    | otherwise    = m : merge (map (avoid m) xss)
    where
      m = minimum [head xs | xs<-xss, xs/=[]]
      avoid m (x:xs) | m==x  = xs
      avoid m   xs           = xs

(感谢MtnViewMark的评论,代码从原始版本中清理完毕.)这有效:

*Main> take 20 $ multiples [4,6,9]
[4,6,8,9,12,16,18,20,24,27,28,30,32,36,40,42,44,45,48,52]

这种实现merge比一次合并两个列表更有效,并且生成每个输出元素只需要O(n)时间.

每个元素O(log n)

更多(和AFAICT,最有效)算法是通过将候选者保持在堆中来生成所需的倍数.每个输出元素只需要O(log n)时间.

import Data.Heap as Heap (MinHeap, insert, empty, view)

multiplesH xs = uniq $ tail $ map fst $ iterate (next . snd) (0, prep xs)
    where
      prep :: Ord a => [a] -> MinHeap (a,a)
      prep = foldr (\x -> insert (x,x)) empty
      next h = case view h of Just ((x,n),hh) -> (x, insert (x+n,n) hh)
      uniq (x:y:ys) | x==y  = uniq (y:ys)
      uniq (x:xs)           = x: (uniq xs)
      uniq []               = []

当你只有几个数字时,它们没有太大的不同,但是对于大数n,堆版本要快得多:

*Main> :set +s
*Main> multiples [1000..2000] !! 10000
20088
(21.70 secs, 2108213464 bytes)
*Main> multiplesH [1000..2000] !! 10000
20088
(0.08 secs, 15348784 bytes)

Answer 2

multi xs = [x*y | y <- [1..], x <- xs ]

应该这样做。主要问题是有点难以控制应该使用多少个数字take。

为了避免结果中出现多个相同的数字，请在结果列表上应用 Data.List.nub。这并不是非常复杂，可以更快地完成，但可以完成工作。