Haskell中的Hamming数

Question

我需要定义仅素数因子为2，3和5的数的列表，即Hamming数。(即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..]]

Answer 1

我可以使用factors函数来实现，也可以使用其他方法。

我建议不这样做。

一种简单的方法是实现一个函数，该函数获取一个数的质因式分解，然后您就可以拥有

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

然后将其用于过滤所有正整数的列表：

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

另一种更有效的方法是避免除法和过滤，只创建一个包含Hamming数字的列表。

一种简单的方法是利用数n是Hamming数的事实当且仅当

• n == 1，or
• n == 2*k，其中or
• n == 3*k，是Hamming数，or
• n == 5*k，其中k是Hamming数。

然后，您可以创建所有Hamming数字的列表，如下所示

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

其中mergeUnique将两个已排序的列表合并在一起，删除重复项。

这已经相当高效了，但是it can be improved by avoiding producing duplicates from the beginning。

Answer 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)。

给定任何(i,j,k)，elem (i,j,k) T应在有限时间内返回True。

听起来耳熟吗？你可以回想起你之前问过的问题：haskell infinite list of incrementing pairs

在这个问题中，hammar给出了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]