(这很令人兴奋!)我知道,主题是众所周知的.最先进的(在Haskell以及其他语言中)有效生成汉明数字的无限增加序列,没有重复和没有遗漏,长期以来一直是如此(AFAIK - 并且它等同于原始Edsger Dijkstra的代码)太):
hamm :: [Integer]
hamm = 1 : map (2*) hamm `union` map (3*) hamm `union` map (5*) hamm
where
union a@(x:xs) b@(y:ys) = case compare x y of
LT -> x : union xs b
EQ -> x : union xs ys
GT -> y : union a ys
我问的问题是,你能找到让它在任何重要方面更有效的方法吗？它仍然是最先进的技术还是实际上可以通过两次更快的速度和更好的经验增长启动来改善这一点？
如果您的答案是肯定的,请显示代码,并与上述相比,讨论其速度和经验增长顺序(它的运行速度约为~ n^1.05 .. n^1.10前几十万个数字).此外,如果它存在,这个有效的算法是否可以扩展到生成一系列具有任何给定素数的平滑数？
创建
:: [(Integer, Integer)]包含表单对的无限列表对(m,n),其中m和n中的每一个都是其成员[0 ..].另一个要求是,如果(m,n)是列表的合法成员,那么(elem (m,n) pairs)应该True在有限的时间内返回.违反此要求的对的实现被认为是非解决方案.
****新编辑感谢您的评论,让我们看看我是否可以取得一些进展****
pairs :: [(Integer, Integer)]
pairs = [(m,n) | t <- [0..], m <- [0..], n <-[0..], m+n == t]
像这样的东西？我只是不知道它会在有限的时间内返回True.
我觉得这个问题措辞的方式elem不一定是我答案的一部分.如果你打电话(elem (m,n) pairs)它应该返回true.听起来不对？