2

我需要定义其唯一素因数为 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..]]
4

2 回答 2

11

I may do it using the factors function, or otherwise.

I recommend doing it otherwise.

One simple way is to implement a function getting the prime factorization of a number, and then you can have

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

which would then be used to filter the list of all positive integers:

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

Another way, more efficient is to avoid the divisions and the filtering, and create a list of only the Hamming numbers.

One simple way is to use the fact that a number n is a Hamming number if and only if

  • n == 1, or
  • n == 2*k, where k is a Hamming number, or
  • n == 3*k, where k is a Hamming number, or
  • n == 5*k, where k is a Hamming number.

Then you can create the list of all Hamming numbers as

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

where mergeUnique merges two sorted lists together, removing duplicates.

That’s already rather efficient, but it can be improved by avoiding producing duplicates from the beginning.

于 2013-03-23T17:52:29.130 回答
2

请注意，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).
给定 any (i,j,k)，elem (i,j,k) T应该在有限时间内返回 True 。
听起来很熟悉？你可以回忆一下你之前问过的问题： haskellinfinite list of incrementing pairs

在那个问题中，哈马尔给出了配对的答案。我们可以将其推广到三元组。

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]
于 2013-03-23T18:51:29.140 回答