Najbardziej eleganckie kombinacje elementów w F #

Question

Jeszcze jedno pytanie o najbardziej elegancką i prostą implementację kombinacji elementów w F #.

Powinno zwrócić wszystkie kombinacje elementów wejściowych (List lub Sekwencja). Pierwszy argument to liczba elementów w połączeniu.

Na przykład:

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

Answer 1

jeden mniej zwięzły i szybsza rozwiązanie niż 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

jest więcej wersji consise odpowiedzi KvB za:

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

Moje rozwiązanie jest mniej zwięzły, mniej skuteczne (chociaż nie bezpośredni rekurencji używane), ale to w pełni zwraca wszystkie kombinacje (obecnie tylko pary, trzeba rozszerzyć filterOut, aby mógł zwrócić krotkę dwóch list, zrobi trochę później).

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 

grzebień [1, 2, 3, 4] powróci: [[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, tak tylne kombinacji trochę odmienne podejście (bez korzystania z funkcji biblioteki)

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

Przyjęty odpowiedź wspaniały i szybko zrozumiały, jeśli znasz rekursję drzewa. Ponieważ szukano elegancji, otwarcie tej długiej, uśpionej nitki wydaje się nieco niepotrzebne.

Jednak wymagało prostszego rozwiązania. Iteracyjne algorytmy czasem wydają mi się prostsze. Ponadto wydajność została wymieniona jako wskaźnik jakości, a iteracyjne procesy są czasem szybsze niż rekursywne.

Poniższy kod jest rekursywny i generuje proces iteracyjny. Wymaga to jednej trzeciej czasu na obliczenie kombinacji wielkości 12 z listy 24 elementów.

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

Pomysł, który pozwala iteracyjny proces jest wstępnie obliczyć mapa ostatniego wybranego elementu do listy pozostałych dostępnych elementów. Ta mapa jest przechowywana w remainderAfter.

Kod nie jest zwięzły ani nie jest zgodny z licznikiem i rymowanką.

Answer 7

Implementacja naiwna na podstawie wyrażenia sekwencji. Osobiście często uważam, że wyrażenia sekwencji są łatwiejsze do naśladowania niż inne bardziej gęste funkcje.

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

Metoda pochodzi z Matematyka dyskretna i jej zastosowań. Wynik zwraca uporządkowaną listę kombinacji przechowywanych w tablicach. Indeks jest oparty na indeksie.

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

To rozwiązanie jest proste i funkcji pomocnika kosztuje stałą pamięć.