Wie man über alle Teilmengen einer Reihe von Zahlen iteriert, die zu ungefähr 0 reichen

Question

Jetzt habe ich mich nicht für die funktionale Programmierung für, oh, fast 20 Jahre, wenn wir nicht viel weiter als das Schreiben von Fakultäten und fibs, also appelliere ich wirklich an die Community um Hilfe bei der Suche nach einer Lösung.

Mein Problem ist folgendes: „eine Gruppe von Handelsobjekten gegeben, ich will alle Kombinationen von Geschäften finden, die Netto-Null +/- gewisse Toleranz“

Meine Vorspeise für zehn ist:

let NettedOutTrades trades tolerance = ... 

sich mein Ausgangspunkt annimmt, ist ein zuvor konstruierten Array von Tupeln (Handel, Wert). Was ich will, ist ein Array (oder eine Liste, was auch immer) von Arrays von Trades, die herauskommen. Also:

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

würde zu:

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

Ich denke, dass dies mit einem Schwanz rekursive Konstrukt erreicht werden könnte, zwei Akkumulatoren mit - einer für die Ergebnisse und einen für die Summe des Handels Werte. Aber wie bringt man alles zusammen ...?

Ich bin mir sicher, dass ich mit C# etwas prozesstechnisches Verfahren ausschalten konnte, aber es fühlt sich einfach nicht nach dem richtigen Werkzeug an - ich bin davon überzeugt, dass es eine elegante, prägnante und effiziente Lösung geben wird Paradigma ... Ich bin einfach nicht gut genug geübt, um es jetzt zu identifizieren!

Answer 1

Da @Tomas bereits eine direkte Lösung gab, dachte ich, ich würde eine Lösung präsentieren, die die Zusammensetzung mit Funktionen höherer Ordnung als leistungsfähige Technik hervorhebt, die häufig in der funktionalen Programmierung verwendet wird; Dieses Problem kann in drei diskrete Schritte zerlegt werden:

1. Generieren Sie alle Kombinationen eines Satzes von Elementen. Dies ist das schwierigste und wiederverwendbarste Teil des Problems. Daher isolieren wir diesen Teil des Problems in eine eigenständige Funktion, die eine Sequenz von Kombinationen mit einer generischen Liste von Elementen zurückgibt.
2. Gegebene Liste von (Handel, Wert), filtern Sie alle Kombinationen mit Wert Summen nicht innerhalb einer gegebenen Toleranz.
3. Ordnen Sie jede Kombination einer Liste von (Handel, Wert) zu einer Handelsliste zu.

I @ Tomas zugrunde liegenden Algorithmus angehoben alle für die Berechnung (erwarten, dass die leeren) Kombinationen eines Satzes, sondern verwenden eine rekursive Sequenz Ausdruck anstelle einer rekursiven Funktion mit einem Akkumulator (ich diesen etwas leichter finden lesen und schreiben) .

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) 

Ich tauschte die Reihenfolge des trades und tolerance in Ihrer vorgeschlagenen Funktion Signatur, da sie es einfacher, Curry durch Toleranz und Rohr in (Handel, Wert) Listen machen, die der typische Stil in der F # Gemeinde verwendet wird, und allgemein unterstützt von der F # -Bibliothek. Beispiel:

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

Answer 2

Hier ist eine funktionale Möglichkeit, die gewünschte Funktion zu schreiben. Es ist eine einfache funktionale Implementierung ohne intelligente Optimierungen, die Listen verwenden. Es ist nicht Schwanz-rekursiv, weil sie sich selbst rekursiv zwei Mal für jeden Handel aufrufen muss:

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

Die Funktion verarbeitet rekursiv alle Kombinationen, so ist es nicht besonders effizient (aber es ist wahrscheinlich nicht besser Weg). Es ist tail-rekursiv nur im zweiten Aufruf an loop, aber um es vollständig tail-rekursiv zu machen, müssten Sie Fortsetzungen, die das Beispiel ein bisschen komplexer machen würde.

Answer 3

Das war interessant. Ich entdeckte, dass es zwei Arten von Fortsetzungen gibt: Eine Builder-Fortsetzung und eine Verarbeitungsfortsetzung.

Wie auch immer; Dies ist dem Teilmengenproblem sehr ähnlich, das NP-vollständig ist. Daher gibt es wahrscheinlich keinen schnelleren Algorithmus, als alle Möglichkeiten aufzuzählen und diejenigen auszuwählen, die dem Kriterium entsprechen.

Sie müssen jedoch keine Datenstruktur aus den generierten Kombinationen erstellen. Wenn es effizienter ist, nur eine Funktion mit jedem Ergebnis aufzurufen.

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

Zum Beispiel:

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

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

Der Grund einer Builder Fortsetzung für die Verwendung anstelle einem Akkumulator ist, dass Sie das Ergebnis in derselben Reihenfolge erhalten, wie in vergangen war, ohne es umkehren zu müssen.