How to iterate over all subsets of a set of numbers that sum to around 0

Question

Now, I haven't applied myself to functional programming for, oh, nearly 20 years, when we didn't get much further than writing factorials and fibs, so I'm really appealing to the community for some help in finding a solution.

My problem is this:

"Given a group of trade objects, I want to find all the combinations of trades that net to zero +/- some tolerance."

My starter for ten is:

let NettedOutTrades trades tolerance = ...

Let's assume my starting point is a previously constructed array of tuples (trade, value). What I want back is an array (or list, whatever) of arrays of trades that net out. Thus:

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

would result in:

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

I'm thinking that this could be achieved with a tail recursive construct, using two accumulators - one for the results and one for the sum of trade values. But how to put it all together...?

I'm sure I could knock out something procedural using c#, but it just doesn't feel like the right tool for the job - I'm convinced there's going to be an elegant, concise, efficient solution using the functional paradigm...I'm just not well practiced enough to identify it at present!

Answer 1

Here is one functional way to write the function you want. It is a straightforward functional implementation without any clever optimizations that uses lists. It isn't tail-recursive, because it needs to call itself recursively two times for each trade:

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 [] [] 

The function recursively processes all combinations, so it is not particularly efficient (but there probably isn't any better way). It is tail-recursive only in the second call to loop, but to make it fully tail-recursive, you'd need continuations, which would make the example a bit more complex.