optimization - resueltos - teoria de conjuntos operaciones

Cómo iterar sobre todos los subconjuntos de un conjunto de números que suman alrededor de 0

Question

Ahora, no me he aplicado a la programación funcional durante, casi 20 años, cuando no llegamos mucho más allá de escribir factoriales y fibs, por lo que estoy realmente apelando a la comunidad para que me ayude a encontrar una solución.

Mi problema es este:

"Dado un grupo de objetos comerciales, quiero encontrar todas las combinaciones de intercambios que den lugar a cero +/- algo de tolerancia".

Mi arranque para diez es:

let NettedOutTrades trades tolerance = ...

Supongamos que mi punto de partida es una matriz previamente construida de tuplas (comercio, valor). Lo que quiero volver es una matriz (o lista, lo que sea) de matrices de intercambios que se redireccionan. Así:

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

daría como resultado:

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

Estoy pensando que esto podría lograrse con una construcción recursiva de cola, usando dos acumuladores: uno para los resultados y otro para la suma de los valores de comercio. Pero, ¿cómo ponerlo todo junto ...?

Estoy seguro de que podría eliminar algo de procedimiento usando c #, pero simplemente no se siente como la herramienta adecuada para el trabajo. Estoy convencido de que va a haber una solución elegante, concisa y eficiente usando el paradigma funcional ... ¡No estoy lo suficientemente bien entrenado como para identificarlo en este momento!

Answer 1

Aquí hay una forma funcional de escribir la función que desea. Es una implementación funcional directa sin optimizaciones inteligentes que utiliza listas. No es recursivo de cola, porque necesita llamarse recursivamente dos veces para cada operación:

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

La función procesa de forma recursiva todas las combinaciones, por lo que no es particularmente eficiente (pero probablemente no exista una forma mejor). Es recursivo de cola solo en el segundo loop llamada a loop , pero para que sea totalmente recursivo de cola, necesitaría continuaciones , lo que haría el ejemplo un poco más complejo.

Answer 2

Esto fue interesante Descubrí que hay dos tipos de continuación: una continuación del generador y una continuación del procesamiento.

De todas formas; Esto es muy similar al problema de Subset-Sum, que es NP-completo. Por lo tanto, probablemente no haya un algoritmo más rápido que el de enumerar todas las posibilidades y elegir aquellas que coincidan con el criterio.

Sin embargo, en realidad no necesita construir una estructura de datos a partir de las combinaciones que se generan. Si fuera más eficiente simplemente llamar a una función con cada resultado.

/// 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

Por ejemplo:

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

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

El motivo por el que se utiliza una continuación de generador en lugar de un acumulador es que obtiene el resultado en el mismo orden en que se transfirió, sin tener que revertirlo.

Answer 3

Como @Tomas ya dio una solución directa, pensé que presentaría una solución que destaca la composición con funciones de orden superior como una poderosa técnica comúnmente utilizada en la programación funcional; este problema se puede descomponer en tres pasos discretos:

1. Genera todas las combinaciones de un conjunto de elementos. Esta es la pieza más difícil y reutilizable del problema. Por lo tanto, aislamos esta parte del problema en una función independiente que devuelve una secuencia de combinaciones dada una lista genérica de elementos.
2. Dada la lista de (comercio, valor), filtre todas las combinaciones con sumas de valor que no estén dentro de una tolerancia dada.
3. Asigne cada combinación de una lista de (comercio, valor) a una lista de comercio.

Levanté el algoritmo subyacente de @Tomas para calcular todas las combinaciones (esperar el vacío) de un conjunto, pero utilizo una expresión de secuencia recursiva en lugar de una función recursiva con un acumulador (me resulta un poco más fácil de leer y escribir).

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)

Cambié el orden de los trades y la tolerance en la firma de función propuesta, ya que facilita curry por tolerancia y canalización en listas (comerciales, de valor) que es el estilo típico utilizado en la comunidad F # y generalmente fomentado por la biblioteca F #. p.ej:

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