Hamming Numbers Variant
 |
||
|
Hamming Numbers Variant |
|
Hamming numbers是指那些只能被2、3和5整除的数。这个序列是Sloane中的A051037（http://www.research.att.com/~njas/sequences/A051037）。最初的几个Hamming numbers是
我们的任务是以递增的顺序生成这些数字。这个任务是惰性列表有用的一个著名例子。事实上，本代码和HammingNumbers页面上的代码都使用了惰性列表作为解决方案。第三个实现可以在Mark Jason Dominus的《Higher Order Perl》（http://hop.perl.plover.com/）中找到。我想感谢这两个实现的所有者提供的想法。
那么，让我们看看惰性列表解决方案是如何进行的。
我们将惰性列表定义为对列表第一个元素和列表其余部分的承诺。（大多数其他人定义惰性列表的方式略有不同：对第一个元素和列表其余部分的承诺。我更喜欢使用第一种方法，但在这里没有太大的区别。）
现在，经典地，我们可以这样生成Hamming序列
hamming := cons(1, merge(map(x -> 2*x, Hamming), merge(map(x -> 3*x, Hamming), map(x -> 5*x, Hamming))));
其中，cons(a, d) 从第一个元素a和列表其余部分d创建一个列表；map(f, x) 返回一个列表，该列表的每个元素都是将函数f应用到x的相应元素的结果；merge(a, b) 将两个已排序的列表合并成另一个已排序的列表；x -> n*x 是一个将输入乘以n的一元函数；并且这些操作足够惰性。
这个解决方案利用了这样一个事实：一个数是Hamming number，当且仅当它等于1，或者它是2乘以一个Hamming number，或者它是3乘以一个Hamming number，或者它是5乘以一个Hamming number。
这个方法的问题在于：有些数字会被多次生成。例如，6既是2乘以一个Hamming number，又是3乘以一个Hamming number。因此，为了使这个方法奏效，你必须以这样一种方式定义merge，使其将公共元素只添加到结果列表中一次。
然而，还有另一种生成Hamming numbers的方法。为此，我们称一个数是Very Hamming，当且仅当它的素数因子只有2和3。然后，我们从2的幂生成，然后从这些生成Very Hamming numbers，再从这些生成Hamming numbers。
2的幂很容易：一个数是2的幂，当且仅当它等于1，或者它是2乘以一个2的幂。现在注意，一个数是Very Hamming，当且仅当它是2的幂，或者它是3乘以一个Very Hamming number。类似地，一个数是Hamming，当且仅当它是Very Hamming，或者它是5乘以一个Hamming number。注意这个是如何每个数字在每个序列中只生成一次的。
相应的公式是这样的。
然而，这并不能按原样工作。原因如下。这些序列的方程是正确的，但它们不足以生成序列，因为当你尝试计算它们时，你会陷入无限循环。为什么会这样？
第一个序列two_power没问题。但是假设你想得到very_hamming列表的第一个元素。为此，你必须计算two_power的第一个元素，以及map(x -> 3*x, very_hamming)的第一个元素，并取两者中较小的一个。但是，要计算map(x -> 3*x, very_hamming)的第一个元素，你必须计算very_hamming的第一个元素。这是一个无限递归。
我们知道very_hamming的第一个元素是two_power的第一个元素，即1。然而，从定义中看不清楚这一点，因为为了知道这一点，你需要知道map(x -> 3*x, very_hamming)的第一个元素大于1。然而，在你不知道very_hamming的第一个元素之前，你无法得知这一点。
为了解决这个问题，你必须明确地告诉程序very_hamming的前几个元素以及hamming的前几个元素。在做出这些更改后，该算法确实有效。
现在让我们看看程序。
第一部分是我从HammingNumbers verbatim复制过来的bignum库。第二部分定义了promise操作，第三部分定义了pair。这两部分都被当作抽象数据类型。第四部分定义了一些用于惰性列表的函数，包括map和merge。最后一部分定义了Hamming numbers序列并打印出其中一些。
-- hamming.lua hamming numbers example -- see https://lua-users.lua.ac.cn/wiki/HammingNumbers -- this code is unoptimized -- bignums ----------------------------------------------------------- -- bignum library do -- very limited bignum stuff; just enough for the examples here. -- Please feel free to improve it. local base = 1e15 local fmt = "%015.0f" local meta = {} function meta:__lt(other) if self.n ~= other.n then return self.n < other.n end for i = 1, self.n do if self[i] ~= other[i] then return self[i] < other[i] end end end function meta:__eq(other) if self.n == other.n then for i = 1, self.n do if self[i] ~= other[i] then return false end end return true end end function meta:__mul(k) -- If the base where a multiple of all possible multipliers, then -- we could figure out the length of the result directly from the -- first "digit". On the other hand, printing the numbers would be -- difficult. So we accept the occasional overflow. local offset = 0 if self[1] * k >= base then offset = 1 end local carry = 0 local result = {} local n = self.n for i = n, 1, -1 do local tmp = self[i] * k + carry local digit = tmp % base carry = (tmp - digit) / base result[offset + i] = digit end if carry ~= 0 then n = n + 1 if offset == 0 then for i = n, 2, -1 do result[i] = result[i - 1] end end result[1] = carry end result.n = n return setmetatable(result, meta) end -- Added so that Fib would work; other must be a Bignum function meta:__add(other) local result = {} if self.n < other.n then self, other = other, self end local n, m = self.n, other.n local diff = n - m local carry = 0 local result = {} for i = m, 1, -1 do local tmp = self[i + diff] + other[i] + carry if tmp < base then carry = 0 else tmp = tmp - base carry = 1 end result[i + diff] = tmp end for i = diff, 1, -1 do local tmp = self[i] + carry if tmp < base then carry = 0 else tmp = tmp - base carry = 1 end result[i] = tmp end if carry > 0 then n = n + 1 for i = n, 2, -1 do result[i] = result[i - 1] end result[1] = carry end result.n = n return setmetatable(result, meta) end function meta:__tostring() local tmp = {} tmp[1] = ("%.0f"):format(self[1]) for i = 2, self.n do tmp[i] = fmt:format(self[i]) end return table.concat(tmp) end function Bignum(k) return setmetatable({k, n = 1}, meta) end end -- promises ---------------------------------------------------------- function delay(f) return {promise_tag = true; promise_func = f}; end; function force(p) if not p.promise_tag then error("forcing a non-promise object of type "..type(p)) end; local f = p.promise_func; if f then local x = f(); p.promise_val, p.promise_func = x, nil; return x; else return p.promise_val; end; end; -- pairs ------------------------------------------------------------- -- we need only infinite lists so we won't mess with nulls here function cons(a, d) return {pair_car = a, pair_cdr = d}; end; function car(c) return c.pair_car; end; function cdr(c) return c.pair_cdr; end; -- lazy lists -------------------------------------------------------- -- a lazy list is a promise to a pair whose cdr is a lazy list -- access fields (thus forcing the list) function lcar(l) return car(force(l)); end; function lcdr(l) return cdr(force(l)); end; -- map a lazy list function lmap(f, l) return delay(function() return cons(f(lcar(l)), lmap(f, lcdr(l))); end); end; -- merge two nondecreasing lazy lists to a lazy list function lmerge(a, b) return delay(function() local x, y = lcar(a), lcar(b); if x <= y then return cons(x, lmerge(lcdr(a), b)); else return cons(y, lmerge(a, lcdr(b))); end; end); end; -- iterate a lazy list function lforeach(f, l) f(lcar(l)); return lforeach(f, lcdr(l)); end; function lany(f, l) x = f(lcar(l)); if x then return x; else return lany(f, lcdr(l)); end; end; -- main ------------------------------------------------------------ --dofile "dump.lua"; -- sequence of natural numbers local N; N = delay(function() return cons(1, lmap(function(x) return x + 1; end, N)) end); -- sequence of Hamming numbers local timeser = function(x) return function(y) return y * x; end; end; local H2; H2 = delay(function() return cons(Bignum(1), lmap(timeser(2), H2)); end); local H3; H3 = delay(function() return cons(Bignum(1), delay(function() return cons(Bignum(2), lcdr(lcdr(lmerge(lmap(timeser(3), H3), H2))) ); end) ); end); local H5; H5 = delay(function() return cons(Bignum(1), delay(function() return cons(Bignum(2), lcdr(lcdr(lmerge(lmap(timeser(5), H5), H3))) ); end) ); end); local n, m = 1, 500005; lany(function(a) if 0 == n % 50000 or n <= 200 then print(n, a); end; n = n + 1; return m <= n; end, H5); -- END
