Die meisten eleganten Kombinationen von Elementen in F #

Question

Noch eine Frage zur elegantesten und einfachsten Implementierung von Elementkombinationen in F #.

Es sollte alle Kombinationen von Eingabeelementen (entweder Liste oder Sequenz) zurückgeben. Erstes Argument ist die Anzahl der Elemente in einer Kombination.

Zum Beispiel:

comb 2 [1;2;2;3];; 
[[1;2]; [1;2]; [1;3]; [2;2]; [2;3]; [2;3]] 

Answer 1

Eine weniger prägnant und schnellere Lösung als ssp:

let rec comb n l = 
    match n, l with 
    | 0, _ -> [[]] 
    | _, [] -> [] 
    | k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs 

Answer 2

let rec comb n l = 
    match (n,l) with 
    | (0,_) -> [[]] 
    | (_,[]) -> [] 
    | (n,x::xs) -> 
     let useX = List.map (fun l -> x::l) (comb (n-1) xs) 
     let noX = comb n xs 
     useX @ noX 

Answer 3

Es gibt mehr consise Version Antwort der KVB:

let rec comb n l = 
    match (n,l) with 
    | (0,_) -> [[]] 
    | (_,[]) -> [] 
    | (n,x::xs) -> 
     List.flatten [(List.map (fun l -> x::l) (comb (n-1) xs)); (comb n xs)] 

Answer 4

Meine Lösung ist weniger prägnant, weniger wirksam (altho, keine direkte Rekursion verwendet), aber es gibt trully alle Kombinationen zurück (zZ nur Paare, muss FilterOut verlängern, also kann es ein Tupel von zwei Listen zurückbringen, tut wenig später).

let comb lst = 
    let combHelper el lst = 
     lst |> List.map (fun lstEl -> el::[lstEl]) 
    let filterOut el lst = 
     lst |> List.filter (fun lstEl -> lstEl <> el) 
    lst |> List.map (fun lstEl -> combHelper lstEl (filterOut lstEl lst)) |> List.concat 

comb [1; 2; 3; 4] zurück: [[1; 2]; [1; 3]; [1; 4]; [2; 1]; [2; 3]; [2; 4]; [3; 1]; [3; 2]; [3; 4]; [4; 1]; [4; 2]; [4; 3]]

Answer 5

Ok, nur Schwanz Kombinationen wenig anders Ansatz (ohne Bibliotheksfunktion)

let rec comb n lst = 
    let rec findChoices = function 
     | h::t -> (h,t) :: [ for (x,l) in findChoices t -> (x,l) ] 
     | [] -> [] 
    [ if n=0 then yield [] else 
      for (e,r) in findChoices lst do 
       for o in comb (n-1) r do yield e::o ] 

Answer 6

Die akzeptierte Antwort ist wunderschön und schnell verständlich, wenn Sie mit Baumrekursion vertraut sind. Da Eleganz gesucht wurde, scheint das Öffnen dieses langen, schlafenden Fadens etwas unnötig zu sein.

Es wurde jedoch eine einfachere Lösung gefordert. Iterative Algorithmen erscheinen mir manchmal einfacher. Darüber hinaus wurde Leistung als Qualitätsindikator genannt, und iterative Prozesse sind manchmal schneller als rekursive Prozesse.

Der folgende Code ist tail rekursiv und generiert einen iterativen Prozess. Es erfordert ein Drittel der Zeit, um Kombinationen der Größe 12 aus einer Liste von 24 Elementen zu berechnen.

let combinations size aList = 
    let rec pairHeadAndTail acc bList = 
     match bList with 
     | [] -> acc 
     | x::xs -> pairHeadAndTail (List.Cons ((x,xs),acc)) xs 
    let remainderAfter = aList |> pairHeadAndTail [] |> Map.ofList 
    let rec comboIter n acc = 
     match n with 
     | 0 -> acc 
     | _ -> 
      acc 
      |> List.fold (fun acc alreadyChosenElems -> 
       match alreadyChosenElems with 
       | [] -> aList //Nothing chosen yet, therefore everything remains. 
       | lastChoice::_ -> remainderAfter.[lastChoice] 
       |> List.fold (fun acc elem -> 
        List.Cons (List.Cons (elem,alreadyChosenElems),acc) 
       ) acc 
      ) [] 
      |> comboIter (n-1) 
    comboIter size [[]] 

Die Idee, dass ein iteratives Verfahren erlaubt ist, um eine Liste der verbleibenden verfügbaren Elemente eine Karte des letzten gewählten Elements vorzunehmen zu berechnen. Diese Karte wird in remainderAfter gespeichert.

Der Code ist nicht prägnant, noch entspricht es lyrischen Meter und Reim.

Answer 7

Eine naive Implementierung mit Sequenzausdruck. Persönlich habe ich oft das Gefühl, dass Sequenzausdrücke leichter zu folgen sind als andere dichtere Funktionen.

let combinations (k : int) (xs : 'a list) : ('a list) seq = 
    let rec loop (k : int) (xs : 'a list) : ('a list) seq = seq { 
     match xs with 
     | [] ->() 
     | xs when k = 1 -> for x in xs do yield [x] 
     | x::xs -> 
      let k' = k - 1 
      for ys in loop k' xs do 
       yield x :: ys 
      yield! loop k xs } 
    loop k xs 
    |> Seq.filter (List.length >> (=)k) 

Answer 8

genommen Methode von Diskrete Mathematik und ihre Anwendungen. Das Ergebnis gibt eine geordnete Liste von Kombinationen zurück, die in Arrays gespeichert sind. Und der Index ist 1-basiert.

let permutationA (currentSeq: int []) (n:int) (r:int): Unit = 
    let mutable i = r 
    while currentSeq.[i - 1] = n - r + i do 
     i <- (i - 1) 
    currentSeq.[i - 1] <- currentSeq.[i - 1] + 1 
    for j = i + 1 to r do 
     currentSeq.[j - 1] <- currentSeq.[i - 1] + j - i 
    () 
let permutationNum (n:int) (r:int): int [] list = 
    if n >= r then 
     let endSeq = [|(n-r+1) .. n|] 
     let currentSeq: int [] = [|1 .. r|] 
     let mutable resultSet: int [] list = [Array.copy currentSeq]; 
     while currentSeq <> endSeq do 
      permutationA currentSeq n r 
      resultSet <- (Array.copy currentSeq) :: resultSet 
     resultSet 
    else 
     [] 

Diese Lösung ist einfach und Hilfsfunktion kostet konstant Speicher.