如何迭代总和为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#删除一些程序性的东西,但它只是感觉不适合这项工作的工具 - 我相信使用功能范例会有一个优雅,简洁,高效的解决方案......我目前还没有很好地练习识别它!

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,但为了使它完全是尾递归的,你需要连续性,这会使这个例子更复杂一些.

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