Как перебрать все подмножества набора чисел, сумма которых равна примерно 0

Question

Итак, я почти 20 лет не занимался функциональным программированием, когда мы не продвинулись дальше, чем написание факториалов и выдумок, поэтому я действительно обращаюсь к сообществу за помощью в поискерешение.

Моя проблема заключается в следующем:

"Учитывая группу торговых объектов, я хочу найти все комбинации сделок, которые равны нулю +/- некоторый допуск."

Мой стартовый номер на десять:

let NettedOutTrades trades tolerance = ...

Давайте предположим, что моей отправной точкой является ранее построенный массив кортежей (trade, value).То, что я хочу вернуть, это массив (или список, что угодно) массивов сделок, которые выходят из сети.Таким образом:

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. Данный список (trade, value), filterвсе комбинации со значениями сумм, выходящие за пределы данного допуска.
3. Сопоставить каждую комбинацию из списка (торговля, стоимость) со списком торговли.

Я поднял основу @ Томасаалгоритм для вычисления всех (кроме пустых) комбинаций набора, но с использованием рекурсивного выражения последовательности вместо рекурсивной функции с аккумулятором (я считаю, что это немного проще для чтения и записи).

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 в предлагаемой сигнатуре функции, поскольку он облегчает каррирование по допускам и конвейеру в списках (торговля, значение), что является типичным стилем, используемым в сообществе F # и обычно поощряемым F #библиотека.например:

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

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

Причиной использования продолжения компоновщика вместо аккумулятора является то, что вы получаете результат в том же порядке, в котором он был передан, без необходимости инвертировать его.