Кратные числа чисел в списке

Каждое число в аргументе становится бесконечным списком кратных

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

​​Затем нужно объединить получившиеся списки. Поскольку каждый список гарантированно находится в порядке возрастания, вы можете просто использовать функцию слияния, подобную той, что в конце этой страницы .

Наконец, вы можете удалить дубликаты. Это можно сделать с помощью отсортированного списка:

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

Вот версия, которая всегда дает отсортированные результаты, удаляет дубликаты, создает бесконечный список (из которого можно взять ) и относительно эффективна (должна быть постоянной памятью!):

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

Пример:

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

Примечание: предполагается, что список ввода отсортирован. Добавьте . отсортировать после . преп , чтобы снять это ограничение.

Вот два эффективных решения, которые создают отсортированные бесконечные списки без дубликатов, из которых вы можете взять . Предположим, ваш вход в кратных содержит 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]

Эта реализация слияния является более эффективно, чем объединение списков по два за раз, и для создания каждого элемента вывода требуется всего 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)

Это работает, но не для бесконечных списков:

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

Таким образом, вы должны указать, сколько кратных значений вы хотите в части [1..10]. Плохо, что это не будет уважать [5,4] например, просто сортируя это на одно и то же.

Хорошо, лучше:

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

возьмем кратные 10 $ [4,5]

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

Вы можете добавить туда «кусочек», чтобы удалить двойные числа

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

Я удивлен, увидев, что «проблема Хэмминга» не упоминается: проблема Хэмминга - один из классических примеров ленивого функционального программирования, который Дэвид Тернер представил для своего FP, первого языка, подобного Haskell, Miranda.

Задача Хэмминга такая же, как аналогична кратным [2,3,5] , а решение Тернера (см. Комментарии ниже):

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

(Из Тернера Пример сценария Miranda )

Это напрямую обобщает (при условии, что все элементы, переданные в кратные, больше 1 и, вопреки вопросу, список параметров увеличивается):

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

Было обсуждение четырех видов решения проблемы Хэмминга на LtU: выразительность «идиоматического C ++» .

Другой ответ? Что ж, один из способов истолковать эту проблему - это обобщенное слияние. Я стал немного одержим поиском относительно чистого и эффективного метода многостороннего слияния.

Эта функция слияния принимает на вход любое конечное число произвольных списков и производит их слияние. Единственным условием является сортировка списков. Списки могут быть пустыми или бесконечными:

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

Этот код выполняет только один проход через заголовки входных списков для каждого созданного элемента.

Когда у вас есть это, определить исходную функцию будет просто:

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

Вам понадобится еще одна хорошая обобщенная служебная функция, чтобы исключить повторяющиеся ответы. Названная в честь утилиты unix, вот она:

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

Вы действительно можете превратить этот небольшой фрагмент в полностью работоспособный эквивалент утилиты командной строки uniq (ну, игнорируя параметры командной строки) с помощью всего этого простого кода. :

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

Haskell заставляет меня улыбаться!

Я вижу это как фильтр в списке целые числа.

Все, что вам нужно, это предикат, который определяет, является ли целое число кратным элементу в вашем списке.

А затем отфильтруйте [1 ..] по этому предикату.

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

Возможно:

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

Дает:

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

Haskell не моя сильная сторона и довольно неэффективен для больших списков, но он работает (я думаю! ).

Вам понадобится модуль List : l List в hugs / ghci.