4

我正在尝试生成可以用表格表示的所有倍数的列表2^a*3^b*5^c，其中 a、b 和 c 是整数。我尝试了以下，

[ a * b * c | a <- map (2^) [0..], b <- map (3^) [0..], c <- map (5^) [0..] ]

但它只列出了 5 的幂，从不继续 2 或 3。

编辑：抱歉，我似乎没有充分澄清这个问题。我想要的是一个有序的无限列表，虽然我可以对一个有限列表进行排序，但我觉得好像有一个更有效的解决方案。

4

6 回答 6

4

只有 5 的幂的原因是 Haskell 试图评估每个可能的 c 为 a = 2^0 和 b = 3^0 并且只有当它完成时它才会为 a = 2^0 和 b = 3^1 . 所以这种方式你只能像这样构造一个有限列表：
[ a * b * c | a <- map (2^) [0..n], b <- map (3^) [0..n], c <- map (5^) [0..n] ]
对于给定的 n。

于 2018-11-28T00:11:38.433 回答
3

我的第一个想法是分别从 2、3 和 5 的幂列表开始：

p2 = iterate (2 *) 1
p3 = iterate (3 *) 1
p5 = iterate (5 *) 1

合并两个排序的流也很容易：

fuse [] ys = ys
fuse xs [] = xs
fuse xs@(x : xs') ys@(y : ys')
    | x <= y    = x : fuse xs' ys
    | otherwise = y : fuse xs ys'

但后来我被卡住了，因为fuse p2 (fuse p3 p5)没有做任何有用的事情。它只产生 2、3 或 5 的倍数，从不混合因子。

我想不出一个纯粹的生成解决方案，所以我以集合累加器的形式添加了一些过滤。该算法（这是非常必要的）是：

  1. 将累加器初始化为{1}.
  2. 从累加器中查找并删除最小元素；叫它n。
  3. 发射n。
  4. 添加{2n, 3n, 5n}到累加器。
  5. 如果您需要更多元素，请转到＃2。

累加器是一个集合，因为这很容易让我找到并提取最小的元素（我基本上将它用作优先级队列）。它还处理因计算和计算而产生的重复2 * 3项3 * 2。

Haskell 实现：

import qualified Data.Set as S

numbers :: [Integer]
numbers = go (S.singleton 1)
    where
    go acc = case S.deleteFindMin acc of
        (n, ns) -> n : go (ns `S.union` S.fromDistinctAscList (map (n *) [2, 3, 5]))

这行得通，但有些事情我不喜欢它：

  • 对于我们发出的每个元素 ( n : ...)，我们将最多三个新元素添加到累加器 ( ns `S.union` ... [2, 3, 5]) 中。（“最多三个”，因为其中一些可能是重复的，将被过滤掉。）
  • 这意味着numbers携带稳定增长的数据结构；我们从中消耗的元素越多numbers，累加器就越大。
  • 从这个意义上说，它不是一个纯粹的“流”算法。即使我们忽略稳定增长的数字本身，我们越深入序列，我们也需要更多的内存并执行更多的计算。
于 2018-11-28T07:29:53.577 回答
2

但它只列出了 5 的幂，从不继续 2 或 3。

仅寻址该位。要计算数字2^a*3^0b*5^c，您尝试生成三元组(a,b,c)，但在生成表单时遇到了困难(0,0,c)。这就是为什么你的数字都是形式的2^0*3^0*5^c，即只有 5 的幂。

如果从配对开始，会更容易。要生成所有对(a,b)，您可以沿着表格的对角线工作，

a+b = k

对于每个积极的k. 每个对角线都很容易定义，

diagonal k = [(k-x,x) | x <- [0..k]]

因此，要生成所有对，您只需为 生成所有对角线k<-[1..]。虽然你想要三倍(a,b,c)，但它是相似的，只是沿着平面工作，

a+b+c = k

要生成这样的平面，只需沿着它们的对角线工作，

triagonal k = [(k-x,b,c) | x <- [0..k], (b,c) <- diagonal x]

你去吧。现在只需生成所有“三角”以获得所有可能的三元组，

triples = [triagonal k | k <- [0..]]
于 2018-11-28T02:37:24.747 回答
2

从您的代码：

[ a * b * c | a <- map (2^) [0..], b <- map (3^) [0..], c <- map (5^) [0..] ]

由于map (5^) [0..]是一个无限列表，在第一次迭代aandb时，它会遍历所述无限列表，它不会停止。这就是为什么它被困在5的幂。

这是除算术之外的解决方案。请注意map (2^) [0..]，map (3^) [0..]、 和map (5^) [0..]都是按升序排序的列表。这意味着通常的合并操作适用：

merge []     ys     = ys
merge xs     []     = xs
merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

为方便起见，let xs = map (2^) [0..]; let ys = map (3^) [0..]; let zs = map (5^) [0..].

要获得 2 和 3 的倍数，请考虑以下所述数字的组织：

1, 2, 4, 8, 16, ...
3, 6, 12, 24, 48, ...
9, 18, 36, 72, 144, ...
...

由此看来，您可能希望以下工作：

let xys = foldr (merge . flip fmap xs . (*)) [] ys

但这不起作用，因为从上面的组织中，merge不知道哪一行包含生成的 head 元素，无限地让它不被评估。我们知道上面一行包含所说的 head 元素，所以通过下面的小调整，它终于可以工作了：

let xys = foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xs . (*)) [] ys

对 做同样的事情zs，这是所需的列表：

let xyzs = foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xys . (*)) [] zs

完整代码总结：

merge []     ys     = ys
merge xs     []     = xs
merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

xyzs = let
    xs = map (2^) [0..]
    ys = map (3^) [0..]
    zs = map (5^) [0..]
    xys = foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xs . (*)) [] ys
    in foldr ((\(m:ms) ns -> m : merge ms ns) . flip fmap xys . (*)) [] zs
于 2018-11-28T07:32:13.993 回答
1

另一种看待它的方式是你想要只能被 2,3 或 5 整除的数字。所以检查从 1 开始的每个数字是否满足这个条件。如果是，它是列表的一部分。

someList = [x| x<- [1..], isIncluded x]

其中 isIncluded 是决定 x 是否满足上述条件的函数。要做到这一点，isIncluded 首先将数字除以 2，直到它不能再除以 2。然后对 3 和 5 的新除数也是如此。最后是 1，然后我们知道这个数字只能被 2 整除,3 或 5，仅此而已。

这可能不是最快的方法，但仍然是最简单的方法。

isIncluded :: Int -> Bool  
isIncluded n = if (powRemainder n 2 == 1) then True 
                                          else let q = powRemainder n 2 
                                           in if (powRemainder q 3 == 1) then True 
                                                                          else let p = powRemainder q 3 
                                                                               in if (powRemainder p 5 == 1) then True else False;

powRemainder 是接受数字和基数并返回不能进一步除以基数的数字的函数。

powRemainder :: Int -> Int -> Int
powRemainder 1 b = 1
powRemainder n b = if (n `mod` b) == 0 then powRemainder (n `div` b) b else n

当我运行take 20 someList它时，它会返回[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]。

于 2018-11-28T06:03:32.910 回答
1

正如其他人已经评论的那样，您的核心不起作用，因为它类似于以下命令式伪代码：

for x in 0..infinity:
   for y in 0..infinity:
      for z in 0..infinity:
         print (2^x * 3^y * 5^x)

最里面for的循环需要无限的时间来执行，所以其他两个循环永远不会超过它们的第一次迭代。因此，x和y都坚持 value 0。

这是一个典型的吻合问题：如果我们坚持在取下一个（或）z之前尝试所有的值，我们就会卡在预期输出的一个子集上。我们需要一种更“公平”的方式来选择 的值，以免我们陷入这种方式：这种技术被称为“dovetailing”。yxx,y,z

其他人则展示了一些相吻合的技术。在这里，我只会提到这个control-monad-omega包，它实现了一个易于使用的 dovetailing monad。生成的代码与 OP 中发布的代码非常相似。

import Control.Monad.Omega

powersOf235 :: [Integer]
powersOf235 = runOmega $ do
   x <- each [0..]
   y <- each [0..]
   z <- each [0..]
   return $ 2^x * 3^y * 5^z
于 2018-11-28T10:12:04.810 回答