Eleganteste Kombinationen von Elementen in F #

Question

Noch eine Frage über eleganteste und einfache Implementierung von Elementkombinationen in F #.

Es sollten alle Kombinationen von Eingabeelementen zurückkehren (entweder Liste oder Sequence). 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 ist prägnante Version von KVS Antwort:

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

Die akzeptierte Antwort ist wunderschön und schnell verständlich, wenn man mit Baumrekursion vertraut ist. Da Eleganz gesucht wurde, scheint diesen langen ruhenden Thread geöffnet wird etwas überflüssig.

Es wurde jedoch eine einfachere Lösung gefragt. Iterative Algorithmen scheinen manchmal einfacher zu mir. Des Weiteren wurde die Performance als Indikator für die Qualität erwähnt, und iterative Prozesse sind manchmal schneller als rekursiven.

Der folgende Code ist Schwanz rekursive und erzeugt einen iterativen Prozess. Es erfordert ein Drittel der Menge an Zeit, Kombinationen von Größe zu berechnen 12 aus einer Liste von 24 Elementen.

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, eine Karte des letzten ausgewählten Elements in eine Liste der verbleibenden verfügbaren Elemente vorab zu berechnen. Diese Karte wird in remainderAfter gespeichert.

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

Answer 5

A naiv Implementierung unter Verwendung von Sequenz Ausdruck. Persönlich fühle ich mich oft Rekursionsformeln sind leichter zu folgen 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 6

Methode genommen von Diskrete Mathematik und ihre Anwendungen . Das Ergebnis liefert eine geordnete Liste von Kombinationen in Arrays gespeichert. Und der Index 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.

Answer 7

Meine Lösung ist weniger prägnant, weniger wirksam (altho, keine direkte Rekursion verwendet), aber es gibt trully alle Kombinationen (derzeit nur Paare, müssen FILTEROUT erweitern, so dass es ein Tupel von zwei Listen zurückkehren kann, wird wenig später tun).

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ückzukehren:     [[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 8

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  ]