Числа Хэмминга в Haskell

Мне нужно определить список чисел, единственными простыми делителями которых являются 2, 3 и 5, числа Хэмминга. (Т.е. числа в виде 2^i * 3^j * 5^k. Последовательность начинается с 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …)

Я могу сделать это с помощью функции factors или как-то иначе. factors ниже должен возвращать коэффициенты своего аргумента. Я считаю, что реализовал это правильно.

   factors :: Int -> [Int]
   factors n = [x | x <- [1..(div n 2) ++ n], mod n x == 0]

Я попытался составить список из 2^i * 3^j * 5^k, используя генераторы списков, но застрял при написании охранника:

hamming :: [Int]
hamming = [n | n <- [1..], „where n is a member of helper“]

helper :: [Int]
helper = [2^i * 3^j * 5^k | i <- [0..], j <- [0..], k <- [0..]]

haskell factors hamming-numbers
person john stamos    schedule 23.03.2013    source источник
comment
Кстати, функция factors имеет синтаксическую ошибку. С наименьшим возможным изменением его можно зафиксировать как factors n = [x | x <- [1..(div n 2)] ++ [n], mod n x == 0].   -  person Palec    schedule 27.04.2015

Ответы (2)


arrow_upward
11
arrow_downward

Я могу сделать это с помощью функции factors или как-то иначе.

Я рекомендую сделать это иначе.

Один простой способ — реализовать функцию, получающую простую факторизацию числа, и тогда вы можете получить

isHamming :: Integer -> Bool
isHamming n = all (< 7) $ primeFactors n

который затем будет использоваться для фильтрации списка всех положительных целых чисел:

hammingNumbers :: [Integer]
hammingNumbers = filter isHamming [1 .. ]

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

Один простой способ — использовать тот факт, что число n является числом Хэмминга тогда и только тогда, когда

  • n == 1, or
  • n == 2*k, где k — число Хэмминга, или
  • n == 3*k, где k — число Хэмминга, или
  • n == 5*k, где k — число Хэмминга.

Затем вы можете создать список всех чисел Хэмминга как

hammingNumbers :: [Integer]
hammingNumbers = 1 : mergeUnique (map (2*) hammingNumbers)
                                 (mergeUnique (map (3*) hammingNumbers)
                                              (map (5*) hammingNumbers))

где mergeUnique объединяет два отсортированных списка вместе, удаляя дубликаты.

Это уже довольно эффективно, но его можно улучшить, избегая создания дубликатов с самого начала.

person Daniel Fischer    schedule 23.03.2013
comment
На самом деле, это hammingNumbers эквивалентно [2^i*3^j*5^k | k<-[0..], j<-[0..], i<-[0..]]. Теоретически он содержит все числа Хэмминга, но на практике это всего лишь [1,2,4,8,16,32,...]. - person nymk; 23.03.2013
comment
Итак, как мы можем заставить его создавать все числа Хэмминга? - person john stamos; 24.03.2013
comment
@johnstamos Дайте ему бесконечное время ;-) Вы можете получить их как [2^i * 3^j * 5^k | n <- [0 .. ], k <- [0 .. n], let m = n-k, j <- [0 .. m], let i = m-j]. Но если вы хотите, чтобы они были перечислены в порядке возрастания, предложенная мной стратегия слияния — лучший из известных мне способов. - person Daniel Fischer; 24.03.2013
comment
Большое спасибо Даниил. У меня есть пара вопросов о вашем коде. в isHamming что все (‹ 7) $ primeFactors n делают? Я не вижу функцию all (я предполагаю, что ‹7 является ее частью), $ и что такое простые множители функции? (Поверьте, у меня пока определены только факторы) И в hammingNumbers я еще не видел функции объединения или функции *. - person john stamos; 24.03.2013
comment
all — это функция, которая принимает предикат и список и проверяет, все ли элементы списка удовлетворяют предикату all :: (a -> Bool) -> [a] -> Bool; Для простых множителей (< 7) проверяет, равны ли они 2, 3 или 5. (*) — это просто умножение, а (2*) — операторная секция, поэтому (2*) = \x -> 2*x. Функции primeFactors или union еще нужно написать (или скопировать откуда-то еще). Я полагаю, это упражнение, и для того, чтобы извлечь из него урок, вы должны сделать хотя бы часть себя. Если это не упражнение, просто возьмите код из другого вопроса. - person Daniel Fischer; 24.03.2013
comment
Нет ли способа быть в бесконечном времени и в порядке? - person john stamos; 25.03.2013
comment
@johnstamos Версия с объединением списков создает их в порядке возрастания. Если вы хотите создать список exponentTriples таким образом, чтобы [2^i * 3^j * 5^k | (i,j,k) <- exponentTriples] генерировал их по порядку, это возможно, но мучительно (на мой взгляд, самым простым способом [вероятно, не самым эффективным] было бы сгенерировать числа Хэмминга по порядку и разложить на множители. их для получения показателей). - person Daniel Fischer; 25.03.2013
comment
union не следует путать с union из Data.List. Последний ожидает несортированные конечные списки, а в этом ответе используются отсортированные бесконечные списки. Лучшее имя для требуемой функции — merge, IMO. - person Palec; 27.04.2015
comment
@Palec merge в сортировке слиянием не удаляет дубликаты, так что это имя тоже не идеально. Я выбрал union, думая о наборах, и забыл о существовании Data.List.union. Я не решаюсь использовать что-то ясное, но неуклюжее, как duplicateFreeMerge. У вас есть идея для имени, которое ясно, но не неуклюже? - person Daniel Fischer; 27.04.2015
comment
@DanielFischer mergeUniq в порядке? - person Palec; 27.04.2015
comment
@Палек Спасибо. Однако я решил написать уникальное. - person Daniel Fischer; 28.04.2015

arrow_upward
2
arrow_downward

Обратите внимание, что набор hamming

{2^i*3^j*5^k | (i, j, k) ∈ T}

куда

T = {(i, j, k) | i ∈ [0..], j ∈ [0..], k ∈ [0..]}

Но мы не можем использовать [(i, j, k) | i ‹- [0..], j ‹- [0..], k ‹- [0..]]. Потому что этот список начинается с бесконечного числа троек, таких как (0, 0, k).
Если задано любое (i,j,k), elem (i,j,k) T должно вернуть True за конечное время.
Звучит знакомо? Вы можете вспомнить вопрос, который вы задавали ранее: бесконечный список увеличивающихся пар haskell

В этом вопросе Хаммар дал парный ответ. Мы можем обобщить его на тройки.

triples = [(i,j,t-i-j)| t <- [0..], i <- [0..t], j <- [0..t-i]]
hamming = [2^i*3^j*5^k | (i,j,k) <- triples]
person nymk    schedule 23.03.2013