如何迭代所有和接近0的数字集合的子集

Question

现在，我已经有将近20年没有涉及函数式编程了，当时我们只能写阶乘和斐波那契数列，所以我真的希望社区能够提供一些帮助来找到解决方案。

我的问题是：

“给定一组交易对象，我想找出所有净收益为零+/-某个容差的交易组合。”

我的起点是：

let NettedOutTrades trades tolerance = ...

假设我的起点是一个预先构建好的元组（交易，价值）数组。我想要得到的是一个交易净额的数组（或列表）。因此：

let result = NettedOutTrades [| (t1, -10); (t2, 6); (t3, 6); (t4; 5) |] 1

会导致：

   [| 
     [| t1; t2; t4 |]
     [| t1; t3; t4 |]
   |]

我认为可以使用尾递归构造实现此目标，使用两个累加器-一个用于结果，另一个用于交易值的总和。但是如何将所有内容组合起来呢……？

我确信可以通过使用函数式编程范式的优雅、简洁、高效的解决方案来解决这个问题，虽然我可以用C#编写出一些过程性的东西，但它似乎不是最适合这项工作的工具... 我只是目前还没有足够的经验来确定它！

- Brett

---

你可能想编辑你的示例 - 应该是 **(t1, -11)**，这样才能抵消。 - BrokenGlass

每个交易的问题等价于“子集和问题”（http://en.wikipedia.org/wiki/Subset_sum_problem），该问题是 NP 完全问题。请注意，我已经尽力使翻译更加通俗易懂，但不改变原文的意思。 - BrokenGlass

@BrokenGlass：我认为Brett在原始问题中将1定义为公差间隙（"...that net to zero +/- some tolerance."）。 - froeschli

没错，froeschli，这个例子是为了说明容差的使用而设置的...尽管公平地说，这可能是问题中最微不足道的部分，可以省略以增加清晰度。 - Brett

Answer 1

这里有一个编写你想要的函数的功能性方法。这是一个直接使用列表实现而没有任何巧妙优化的功能性实现。它不是尾递归，因为每次交易需要调用自身两次递归。

let nettedOutTrades trades tolerance =
  // Recursively process 'remaining' trades. Currently accumulated trades are
  // stored in 'current' and the sum of their prices is 'sum'. The accumulator
  // 'result' stores all lists of trades that add up to 0 (+/- tolerance)
  let rec loop remaining sum current result =
    match remaining with 
    // Finished iterating over all trades & the current list of trades
    // matches the condition and is non-empty - add it to results
    | [] when sum >= -tolerance && sum <= tolerance &&
              current <> [] -> current::result
    | [] -> result // Finished, but didn't match condition
    | (t, p)::trades -> 
      // Process remaining trades recursively using two options:
      // 1) If we add the trade to current trades
      let result = loop trades (sum + p) (t::current) result
      // 2) If we don't add the trade and skip it
      loop trades sum current result
  loop trades 0 [] [] 

这个函数递归处理所有组合，因此效率不是特别高（但可能没有更好的方法）。它只在第二次对loop的调用中是尾递归的，但要使其完全尾递归，您需要使用continuations，这将使示例变得更加复杂。

- Tomas Petricek

---

+1 @Tomas，你真的很快地完成了这个任务，然后又回来添加了优秀的注释。只有一个小建议：翻转nettedOutTrades函数中的trades和tolerance参数，这样你就可以通过容差进行柯里化，并将交易管道传入其中。 - Stephen Swensen

+1 @Tomas，感谢你提供的绝佳解决方案。我选择了Stephen的答案，因为它将组件分解，并且我可以看到在将来，当我的需求范围（不可避免地）扩大时，它会变得非常有用。 - Brett

Answer 2

由于@Tomas已经提供了直接的解决方案，我想介绍一种强调高阶函数组合作为函数式编程中常用技术的解决方案；这个问题可以分解为三个离散步骤：

1. 生成一组元素的所有组合。这是问题中最难且可重复使用的部分。因此，我们将这部分问题隔离成一个独立的函数，该函数返回给定通用元素列表的组合序列。
2. 给定(交易，价值)列表，过滤掉所有价值总和不在给定容差范围内的组合。
3. 将(交易，价值)列表中的每个组合映射到交易列表中。

我采用了@Tomas的底层算法来计算集合的所有(非空)组合，但使用了递归序列表达式而不是带有累加器的递归函数（我发现这样稍微更易于阅读和编写）。

let combinations input =
    let rec loop remaining current = seq {
        match remaining with 
        | [] -> ()
        | hd::tail -> 
            yield  hd::current
            yield! loop tail (hd::current)
            yield! loop tail current
    }
    loop input []

let nettedOutTrades tolerance trades =
    combinations trades
    |> Seq.filter
        (fun tradeCombo -> 
            tradeCombo |> List.sumBy snd |> abs <= tolerance)
    |> Seq.map (List.map fst)

我在你提出的函数签名中交换了trades和tolerance的顺序，因为这样可以更容易地通过容差进行加工，并且管道（trade,value）列表，这是F#社区通常使用的风格，也是F#库鼓励的风格。例如：

[("a", 2); ("b", -1); ("c", -2); ("d", 1)] |> nettedOutTrades 1

- Stephen Swensen

Answer 3

这很有趣。我发现有两种续延：构建续延和处理续延。

无论如何，这与子集和问题非常相似，该问题是NP完全的。因此，可能没有比枚举所有可能性并选择符合标准的可能性更快的算法。

虽然如此，您实际上不需要从生成的组合中构建数据结构。如果每个结果调用一个函数更有效率。

/// Takes some input and a function to receive all the combinations
/// of the input.
///   input:    List of any anything
///   iterator: Function to receive the result.
let iterCombinations input iterator =
  /// Inner recursive function that does all the work.
  ///   remaining: The remainder of the input that needs to be processed
  ///   builder:   A continuation that is responsible for building the
  ///              result list, and passing it to the result function.
  ///   cont:      A normal continuation, just used to make the loop tail
  ///              recursive.
  let rec loop remaining builder cont =
    match remaining with
    | [] ->
        // No more items; Build the final value, and continue with
        // queued up work.
        builder []
        cont()
    | (x::xs) ->
        // Recursively build the list with (and without) the current item.
        loop xs builder <| fun () ->
          loop xs (fun ys -> x::ys |> builder) cont
  // Start the loop.
  loop input iterator id

/// Searches for sub-lists which has a sum close to zero.
let nettedOutTrades tolerance items =
  // mutable accumulator list
  let result = ref []
  iterCombinations items <| function
    | [] -> () // ignore the empty list, which is always there
    | comb ->
        // Check the sum, and add the list to the result if
        // it is ok.
        let sum = comb |> List.sumBy snd
        if abs sum <= tolerance then
          result := (List.map fst comb, sum) :: !result
  !result

例如：

> [("a",-1); ("b",2); ("c",5); ("d",-3)]
- |> nettedOutTrades 1
- |> printfn "%A"

[(["a"; "b"], 1); (["a"; "c"; "d"], 1); (["a"], -1); (["b"; "d"], -1)]

使用构建器延续而不是累加器的原因是，您可以按照传入的顺序获得结果，而无需将其反转。

- Markus Jarderot