algorithm - 列表中数字的倍数

Question

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

即

take 10 (multiples [4,5])

给予

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

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

Answer 1

这里有两个有效的解决方案，可以生成无重复的排序无限列表，您可以从中获取。假设您对 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)