Как найти список всех чисел, кратных только степеням 2, 3 и 5?

Question

Как найти список всех чисел, кратных только степеням 2, 3 и 5?

Я пытаюсь создать список всех кратных, которые могут быть представлены в форме $2^a*3^b*5^c$ где a, b и c - целые числа. Я попробовал следующее,

[ a * b * c | a <- map (2^) [0..], b <- map (3^) [0..], c <- map (5^) [0..] ]

но он перечисляет только степени 5 и никогда не переходит к 2 или 3.

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

5

haskell hamming-numbers smooth-numbers

Источник

user4282604 27 ноя '18 в 23:42

6 ответов

Другие вопросы по тегам haskell hamming-numbers smooth-numbers

user9921109 28 ноя '18 в 00:11 2018-11-28 00:11 · Answer 1 · 2018-11-28 00:11

Причина, по которой существуют только степени 5, состоит в том, что Haskell пытается оценить все возможные значения c для a = 2^0 и b = 3^0, и только когда он закончится, он перейдет к a = 2^0 и b = 3^1, Таким образом, вы можете построить только конечный список, например так:
[ a * b * c | a <- map (2^) [0..n], b <- map (3^) [0..n], c <- map (5^) [0..n] ]
для данного n.

user1848654 28 ноя '18 в 07:29 2018-11-28 07:29 · Answer 2 · 2018-11-28 07:29

Моя первая идея исходила из списков степеней 2, 3 и 5 соответственно:

p2 = iterate (2 *) 1
p3 = iterate (3 *) 1
p5 = iterate (5 *) 1

Также легко объединить два отсортированных потока:

fuse [] ys = ys
fuse xs [] = xs
fuse xs@(x : xs') ys@(y : ys')
    | x <= y    = x : fuse xs' ys
    | otherwise = y : fuse xs ys'

Но потом я застрял, потому что fuse p2 (fuse p3 p5) не делает ничего полезного. Он производит только кратные 2, 3 или 5, никогда не смешивая факторы.

Я не мог найти чисто генеративное решение, поэтому добавил немного фильтрации в виде набора аккумуляторов. Алгоритм (который является весьма обязательным):

Инициализируйте аккумулятор, чтобы {1},
Найти и удалить наименьший элемент из аккумулятора; назови это n,
Испускают n,
добавлять {2n, 3n, 5n} к аккумулятору.
Перейдите к #2, если вам нужно больше элементов.

Аккумулятор - это набор, потому что он позволяет мне легко находить и извлекать наименьший элемент (в основном я использую его в качестве очереди с приоритетами). Он также обрабатывает дубликаты, возникающие, например, при вычислении обоих 2 * 3 а также 3 * 2,

Реализация на Haskell:

import qualified Data.Set as S

numbers :: [Integer]
numbers = go (S.singleton 1)
    where
    go acc = case S.deleteFindMin acc of
        (n, ns) -> n : go (ns `S.union` S.fromDistinctAscList (map (n *) [2, 3, 5]))

Это работает, но есть вещи, которые мне не нравятся:

Для каждого элемента мы испускаем (n : ...) добавляем до трех новых элементов в аккумулятор (ns `S.union` ... [2, 3, 5]). ("До трех", потому что некоторые из них могут быть дубликатами, которые будут отфильтрованы.)
Это означает numbers несет в себе постоянно растущую структуру данных; чем больше элементов мы потребляем из numbersЧем больше растет аккумулятор.
В этом смысле это не чисто потоковый алгоритм. Даже если мы игнорируем постоянно растущие числа, нам нужно больше памяти и выполнять больше вычислений по мере углубления в последовательность.

user4540658 28 ноя '18 в 07:32 2018-11-28 07:32 · Answer 3 · 2018-11-28 07:32

Из вашего кода:

[ a * b * c | a <- map (2^) [0..], b <- map (3^) [0..], c <- map (5^) [0..] ]

поскольку map (5^) [0..] бесконечный список, после первых итераций a а также b, он перебирает указанный бесконечный список, который не остановится. Вот почему он застрял на уровне 5.

Вот решение кроме арифметики. Обратите внимание, что map (2^) [0..], map (3^) [0..], а также map (5^) [0..] все списки отсортированы в порядке возрастания. Это означает, что применима обычная операция слияния:

merge []     ys     = ys
merge xs     []     = xs
merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

Для удобства, let xs = map (2^) [0..]; let ys = map (3^) [0..]; let zs = map (5^) [0..],

Чтобы получить кратные 2 и 3, рассмотрите следующую организацию указанных чисел:

1, 2, 4, 8, 16, ...
3, 6, 12, 24, 48, ...
9, 18, 36, 72, 144, ...
...

Судя по этому, можно надеяться на следующие работы:

let xys = foldr (merge . flip fmap xs . (*)) [] ys

Но это не работает, потому что из организации выше, merge не знает, какая строка содержит результирующий элемент head, бесконечно оставляя его без оценки. Мы знаем, что в верхнем ряду содержится указанный элемент head, так что после небольшого изменения он наконец работает:

let xys = foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xs . (*)) [] ys

Сделай то же самое против zsи вот вам желаемый список:

let xyzs = foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xys . (*)) [] zs

Полный код в резюме:

merge []     ys     = ys
merge xs     []     = xs
merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

xyzs = let
    xs = map (2^) [0..]
    ys = map (3^) [0..]
    zs = map (5^) [0..]
    xys = foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xs . (*)) [] ys
    in foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xys . (*)) [] zs

user1442575 28 ноя '18 в 02:37 2018-11-28 02:37 · Answer 4 · 2018-11-28 02:37

но он перечисляет только степени 5 и никогда не переходит к 2 или 3.

Обращаясь только к этому биту. Рассчитать числа 2^a*3^0b*5^c Вы пытались создать тройки (a,b,c), но застрял, производя те из формы (0,0,c), Вот почему ваши номера имеют вид 2^0*3^0*5^c, т.е. только полномочия 5.

Это проще, если вы начнете с пар. Произвести все пары (a,b) вы можете работать по диагонали вида,

a+b = k

за каждый позитивk, Каждую диагональ легко определить,

diagonal k = [(k-x,x) | x <- [0..k]]

Таким образом, чтобы получить все пары, вы просто сгенерируете все диагонали для k<-[1..], Вы хотите тройки (a,b,c) хотя, но это похоже, просто работать вдоль самолетов,

a+b+c = k

Чтобы создавать такие самолеты, просто работайте вдоль их диагоналей,

triagonal k = [(k-x,b,c) | x <- [0..k], (b,c) <- diagonal x]

И вот, пожалуйста. Теперь просто сгенерируйте все "триагоналы", чтобы получить все возможные тройки,

triples = [triagonal k | k <- [0..]]

user3234959 28 ноя '18 в 10:12 2018-11-28 10:12 · Answer 5 · 2018-11-28 10:12

Как уже отмечали другие, ваше ядро не работает, потому что оно аналогично следующему обязательному псевдокоду:

for x in 0..infinity:
   for y in 0..infinity:
      for z in 0..infinity:
         print (2^x * 3^y * 5^x)

Самый внутренний for выполнение занимает бесконечное время, поэтому два других цикла никогда не пройдут свою первую итерацию. Как следствие, x а также y оба привязаны к стоимости 0,

Это классическая проблема: если мы будем настаивать на том, чтобы все z прежде чем принять следующий y (или же x), мы застряли на подмножестве предполагаемых выходов. Нам нужен более "справедливый" способ выбора ценностей x,y,z чтобы мы не застревали таким образом: такие техники известны как "ласточкин хвост".

Другие показали некоторые методы ласточкин хвост. Здесь я только упомяну control-monad-omega пакет, который реализует простую в использовании монаду ласточкин хвост. Полученный код очень похож на тот, который выложен в ОП.

import Control.Monad.Omega

powersOf235 :: [Integer]
powersOf235 = runOmega $ do
   x <- each [0..]
   y <- each [0..]
   z <- each [0..]
   return $ 2^x * 3^y * 5^z

user439578 28 ноя '18 в 06:03 2018-11-28 06:03 · Answer 6 · 2018-11-28 06:03

Другой способ взглянуть на это - вы хотели получить числа, которые делятся только на 2,3 или 5. Поэтому проверьте, удовлетворяет ли каждое число, начинающееся с 1, этому условию. Если да, то это часть списка.

someList = [x| x<- [1..], isIncluded x]

где isIncluded - это функция, которая решает, удовлетворяет ли x вышеуказанному условию. Для этого isIncluded делит число сначала на 2, пока оно не может быть разделено дальше на 2. Затем то же самое происходит с новым разделенным числом для 3 и 5. Если в конце есть 1, то мы знаем, что это число делится только на 2, 3 или 5 и ничего больше.

Это может быть не самый быстрый способ, но все же самый простой способ.

isIncluded :: Int -> Bool  
isIncluded n = if (powRemainder n 2 == 1) then True 
                                          else let q = powRemainder n 2 
                                           in if (powRemainder q 3 == 1) then True 
                                                                          else let p = powRemainder q 3 
                                                                               in if (powRemainder p 5 == 1) then True else False;

powRemainder - это функция, которая принимает число и основание и возвращает число, которое нельзя разделить на основание.

powRemainder :: Int -> Int -> Int
powRemainder 1 b = 1
powRemainder n b = if (n `mod` b) == 0 then powRemainder (n `div` b) b else n

с этим, когда я бегу take 20 someList это возвращается [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36],