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

Perhaps:

let howmany = 10 in take howmany (nub (sort [ x * y | x <- [4, 5, 6, 7], y <- [1..howmany] ]))

Gives:

[4,5,6,7,8,10,12,14,15,16]

Haskell isn't my strong point and it's rather inefficient for larger lists, but it works (I think!).

You will need the List module :l List at hugs/ghci.

Answer 2

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

That should do. The main problem is that it is a little hard to control how many numbers you should take.

To avoid multiple equal numbers in the result apply Data.List.nub on the resulting list. This isn't terribly sophisticated and can be done faster but does the job.

Answer 3

This does work, but not for infinite lists:

sort [ x * y | x <- [4, 5], y <- [1..10] ]

Thus you have to specify how many multiples you want inside the [1..10] part. Bad thing is, it won't respect [5,4] for example, just sorting it to the same thing.

---

Okay, a better one:

multiples :: (Num a, Ord a) => [a] -> [a] 
multiples nums = sort $ multiply 1
   where multiply n = map (*n) nums ++ (multiply $ n + 1)

take 10 $ multiples [4,5]

[4,5,8,10,12,15,16,20,20,25]

You might want to add a "nub" there, to remove double numbers

multiples :: (Num a, Ord a) => [a] -> [a] 
multiples nums = sort . nub $ multiply 1
   where multiply n = map (*n) nums ++ (multiply $ n + 1)

Answer 4

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 5

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 6

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.

Answer 7

I see this as a filter on the list of integers.

All you need is a predicate that determines whether an integer is a multiple of an item in your list.

And then filter [1..] by that predicate.

multiples xs = filter (isDividedByAny xs) [1..]
       where isDividedByAny xs int =  any (divides int) xs
                      where divides int elem  = int `mod` elem == 0

Answer 8

I'm surprised to see that "Hamming problem" is not mentioned: the Hamming problem is one of the classical examples of lazy functional programming that David Turner presented for his FP, the first Haskell-like language, Miranda.

The Hamming problem is the same as is similar to multiples [2,3,5], and Turner's solution is (see comments below):

ham = 1 : foldr1 merge [mult 2 ham, mult 3 ham, mult 5 ham]
      where
      mult n x = [n*a|a<-x]
      merge (a:x) (b:y) = a : merge x y,     if a=b
                        = a : merge x (b:y), if a<b
                        = b : merge (a:x) y, if a>b

(From Turner's Example Miranda scripts)

This directly generalises to (assuming all elements passed to multiples are greater than 1 and, contrary to the question, that the parameter list is increasing):

multiples ms = drop 1 mms
      where mms = 1: foldr1 merge (map (mult mms) ms))
            mult x n = [n*a|a<-x]
            merge (a:x) (b:y) = a : merge x y,     if a=b
                              = a : merge x (b:y), if a<b
                              = b : merge (a:x) y, if a>b

There was a discussion of four kinds of solution to the Hamming problem on LtU: expressivity of "idiomatic C++".

Answer 9

Another answer? Well, one way to construe this problem is as a generalized merge. I became a little obsessed with finding both a relatively clean and efficient method of doing a multi-way merge.

This merge function takes any finite number of arbitrary lists as input and produces their merge. The only precondition is that the lists are sorted. The lists can be empty or infinite:

merge :: (Ord a) => [[a]] -> [a]
merge rs =
    case foldr minToFront [] rs of
        []          -> []
        ([]:rs)     ->     merge rs
        ((a:as):rs) -> a : merge (as:rs)
    where
        minToFront a (b:rs) | a `after` b = b:a:rs
        minToFront a  qs                  = a:qs

        []    `after` _     = False
        _     `after` []    = True
        (a:_) `after` (b:_) = a > b

This code makes just one pass through the heads of the input lists for each element produced.

Once you have this, defining the original function is easy:

multiples :: (Num a, Ord a) => [a] -> [a]
multiples = uniq . merge . map (\n -> iterate (+n) n)

You need another nice generalized utility function to strip out repeated answers. Named for the unix utility, here it is:

uniq :: (Eq a) => [a] -> [a]
uniq :: (Eq a) => [a] -> [a]
uniq []                       = []
uniq (a:bs@(b:_)) | a == b    =     uniq bs
uniq (a:bs)                   = a : uniq bs

You can actually turn that little snippit into a fully workable equivalent to the uniq command line utility (well, ignoring command line options) with just this simple code:

main :: IO ()
main = interact (unlines . uniq . lines)

Haskell makes me smile!