时间戳

首页 > 解决方案 > 为什么这个序列生成不起作用？

f# - 为什么这个序列生成不起作用？

问题描述

我面临着生成元素列表的所有 k 组合（不重复）。除了代码中可能的优化之外，我编写了这个函数，我几乎可以肯定它应该可以工作：

// comb :: int -> 'a list -> seq<'a list>
// Generates a sequence of all combinations (no repetition)
let comb k xs =
  // subs :: 'a list -> seq<'a list>
  // Splits a list in its subsequent non-empty tails
  let rec subs xs =
    seq {
      match xs with
      | _::ys -> yield xs
                 yield! subs ys
      | _     -> yield! []
    }

  let rec comb' k xs rs =
    seq {
      for zs in subs xs do
        match k, zs with
        | 0, _                      -> yield rs                        // Solution reached
        | _ when k > List.length zs -> yield! []                       // Safety (and optimizing) guard
        | _, y::ys                  -> yield! comb' (k - 1) ys (y::rs) // Let's go deeper
        | _                         -> yield! []                       // Not a solution
    }

  comb' k xs []

该算法背后的思想是“遍历”所有可能组合的树，并仅选择具有k元素的组合；该subs函数用于生成元素的子集以生成同级子树；也就是说，调用：

Seq.toList <| subs [1..3];;

产生：

[[1;2;3];[2;3];[3]]

也许这部分有点令人困惑，但它不应该是问题的一部分，我认为问题不存在。

该算法不保持元素的顺序，但这不是我的目的所必需的。

制作一个简单的测试用例：

Seq.toList <| comb 2 [1..3];;

我期待三种解决方案：

[[2;1];[3;1];[3;2]]

但实际上它只返回：

[[2;1]]

我使用 VS Code 进行了一些调试，但我并不真正了解执行流程。

有没有人看到问题出在哪里？

更新

我意识到我严重暴露了算法背后的概念。

我将问题的解决方案想象成一棵搜索树；在每一层，子树的根都包含通过连接所有剩余尾部（subs结果）的头部和父节点列表获得的解决方案。

比较尾部的大小和kI 的当前值，可以了解哪些分支实际上可以包含解决方案。

搜索树

标签： f#

解决方案

您的代码几乎是正确的。唯一的问题是 whenxs是空的comb'，subs即使是 0 也将是空的（因为没有非空的尾部）k，但在这种情况下你也应该让步rs。

k这可以通过在 for 循环之外测试 if is 0 并rs在那里产生，然后将 for 循环放入 else 分支（现在您只需要匹配 on zs）来轻松解决：

  let rec comb' k xs rs =
    seq {
      if k = 0 then yield rs
      elif k <= List.length xs then
          for zs in subs xs do
            match zs with
            | y::ys                  -> yield! comb' (k - 1) ys (y::rs) // Let's go deeper
            | []                     -> yield! []                       // Not a solution
    }

推荐阅读