Multiples of Numbers in a List

Question

How would I print the multiples of a list of given numbers in a merged, sorted list?

I.e.

take 10 (multiples [4,5])

gives

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

I've got it working for lists of size 2 or 1 but I need a more general solution :)

Answer 1

Here are two efficient solutions that produce sorted, infinite lists without duplicates, which you can take from. Suppose your input to multiples has n elements.

O(n) per element

First, for each number in the input make an infinite list of its multiples. Then, merge these lists carefully, keeping them sorted and avoiding duplicates. (This is the harder part of the problem.)

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

(Code cleaned up from original version, thanks to MtnViewMark's comments.) This works:

*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]

This implementation of merge is more efficient than merging the lists two at a time, and it takes only O(n) time to produce each element of output.

O(log n) per element

A more (and AFAICT, most) efficient algorithm is to generate the multiples as you need them, by keeping candidates in a heap. This takes only O(log n) time for each output element.

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 []               = []

When you have only a few numbers they're not much different, but for large n the heap version is much faster:

*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

Each number in the argument becomes an infinite list of multiples

multiLists :: [Integer] -> [[Integer]]
multiLists = map (\x -> iterate (+x) x)

Then you need to merge the resulting lists. Since each list is guaranteed to be in ascending order you can just use a merge function like the one at the end of this page.

Finally, you may want to eliminate duplicates. The way to do this with a sorted list is:

sortedNub :: [Integer] -> [Integer]
sortedNub = map head . group

Answer 3

Here's a version that always produces sorted results, removes duplicates, produces an infinite list (which you can take from), and is relatively efficient (should be constant memory!):

multiples :: (Num a, Ord a) => [a] -> [a]
multiples = map (fst.head) . iterate step . prep
    where prep                    = map (\i -> (i,i))
          next (m,i)              = (m+i,i)

          step (p:ps)             = uniq $ insert (next p) ps

          insert q  []            = [q]
          insert q (p:ps) | q > p = p : insert q ps
          insert q  ps            = q : ps

          uniq p@((ma,_):(mb,_):_) | ma == mb = step p
          uniq p                              = p

Example:

> take 20 $ multiples [4,9]
[4,8,9,12,16,18,20,24,27,28,32,36,40,44,45,48,52,54,56,60]

> take 20 $ multiples [4,8,10]
[4,8,10,12,16,20,24,28,30,32,36,40,44,48,50,52,56,60,64,68]

> take 20 $ multiples [4, 9, 20]
[4,8,9,12,16,18,20,24,27,28,32,36,40,44,45,48,52,54,56,60]

Note: assumes the input list is sorted. Add . sort after . prep to remove this constraint.