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

Question

Как бы я распечатать кратные списка заданных чисел в объединенном, отсортированном списке?

* 1003 Т.е. *

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

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

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

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

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

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

Answer 3

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

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]

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

Answer 4

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

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

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)

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

Answer 5

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

Задача Хэмминга аналогична , аналогична multiples [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

(От Тернера Пример сценариев Миранды )

Это прямо обобщает до (при условии, что все элементы, переданные в кратные, больше, чем 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 ++" .

Answer 6

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

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

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

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

Answer 7

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

Это должно сделать.Основная проблема в том, что немного сложно контролировать, сколько чисел вам нужно take.

Чтобы избежать нескольких равных чисел в результате, примените Data.List.nub к результирующему списку.Это не очень сложно и может быть сделано быстрее, но делает работу.

Answer 8

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

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)

Answer 9

Возможно:

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]

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

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