汉明数变体
 |
||
|
汉明数变体 |
|
汉明数是指那些除了 2、3 和 5 之外，不能被其他素数整除的数。这个序列在 Sloane 中是 A051037 (http://www.research.att.com/~njas/sequences/A051037)。前几个汉明数是
我们的任务是按升序生成这些数字。这个任务是懒惰列表为什么有用的一个众所周知的例子。事实上，这个代码和 汉明数 上的代码都使用懒惰列表作为解决方案。第三个实现可以在 Mark Jason Dominus 的 Higher Order Perl 中找到 (http://hop.perl.plover.com/)。我要感谢这两个实现的作者在那里给出的想法。
所以，让我们看看懒惰列表解决方案是如何进行的。
我们将懒惰列表定义为对列表的第一个元素和列表其余部分的承诺。（大多数其他人对懒惰列表的定义略有不同：作为第一个元素和对列表其余部分的承诺的组合。我更喜欢使用第一种方法，但这里没有太大区别。）
现在，经典地我们可以像这样生成汉明序列
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 的一元函数；并且操作足够懒惰。
这个解决方案利用了这样一个事实：一个数字是汉明数当且仅当它等于 1 或它是 2 乘以一个汉明数，或者它是 3 乘以一个汉明数，或者它是 5 乘以一个汉明数。
这种方法的问题在于：有些数字被多次生成。例如，6 既是 2 乘以一个汉明数，又是 3 乘以一个汉明数。因此，为了使这种方法起作用，您必须以这样一种方式定义 merge，即它只将公共元素放入结果列表中一次。
然而，还有另一种生成汉明数的方法。为此，我们称一个数为“非常汉明数”，当且仅当它的唯一素因子是 2 和 3。然后，我们生成 2 的幂，然后从这些幂中生成“非常汉明数”，最后从这些“非常汉明数”中生成汉明数。
2 的幂很容易生成：一个数是 2 的幂，当且仅当它等于 1 或等于 2 乘以一个 2 的幂。现在注意，一个数是“非常汉明数”，当且仅当它是一个 2 的幂或 3 乘以一个“非常汉明数”。类似地，一个数是汉明数，当且仅当它是一个“非常汉明数”或 5 乘以一个汉明数。注意，这种方法可以精确地生成每个序列中的每个数字一次。
相应的公式如下。
然而，这种方法不能直接使用。原因如下。这些序列的方程是正确的，但它们不足以生成序列，因为当您尝试计算它们时，会陷入无限循环。这是为什么呢？
第一个序列 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 的前几个元素。在进行这些更改后，该算法确实可以正常工作。
现在让我们看看程序。
第一部分是 bignum 库，我从 汉明数 中逐字复制而来。第二部分定义了 promise 操作，第三部分定义了对。这两部分都被视为抽象数据类型。第四部分定义了一些用于惰性列表的函数，包括 map 和 merge。最后一部分定义了汉明数序列并打印其中的一些。
-- 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
