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, entonces realmente estoy apelando a la comunidad para que me ayude a encontrar una solución.

Mi problema es el siguiente:

"Dado un grupo de objetos comerciales, que desea encontrar todas las combinaciones de los comercios que neta a cero +/- cierta tolerancia."

Mi plato de diez es:

let NettedOutTrades trades tolerance = ... 

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

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

se traduciría en:

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

estoy pensando que esto podría lograrse con una construcción recursiva cola, usando dos acumuladores - uno para los resultados y uno para la suma del comercio valores. 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 que use la funcionalidad paradigma ... ¡No estoy lo suficientemente bien entrenado como para identificarlo en este momento!

Answer 1

Dado que @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. Generar 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 de elementos genéricos .
2. Dada la lista de (comercio, valor), filtra todas las combinaciones con sumas de valor no dentro de una tolerancia determinada.
3. Identifica cada combinación de una lista de (comercio, valor) en una lista comercial.

Levanté @ algoritmo subyacente de Tomas para el cálculo de todos (esperar que los vacíos) combinaciones de un set, pero usar una expresión de secuencia recursiva en lugar de una función recursiva con un acumulador (Me parece 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 trades y tolerance en su firma función propuesta, ya que hace que sea más fácil de curry por la tolerancia y la tubería en (, el valor del comercio) Listas que es el estilo típico utilizado en el # comunidad F y generalmente alentado por la biblioteca F #. e.g .:

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

Answer 2

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 recursiva de cola, ya que tiene que llamar a sí mismo de forma recursiva dos veces para cada comercio:

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 hay nada mejor camino). Es recursivo de cola solo en la segunda llamada al loop, pero para que sea completamente recursivo, necesitaría continuaciones, lo que haría el ejemplo un poco más complejo.

Answer 3

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

De todos modos; 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 es necesario crear una estructura de datos 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)] 

La razón para usar una continuación constructor en lugar de un acumulador es que se obtiene el resultado en mismo orden que fue aprobada en, sin tener que revertirla.