Combinaisons d'éléments les plus élégantes dans F #

Question

Encore une question sur l'implémentation la plus élégante et la plus simple des combinaisons d'éléments en F #.

Il doit renvoyer toutes les combinaisons d'éléments d'entrée (Liste ou Séquence). Le premier argument est le nombre d'éléments dans une combinaison.

Par exemple:

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

Answer 1

Un moins concis et plus rapide solution que 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

Il y a plus de version concise de la réponse de 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

Ma solution est moins concise, moins efficace (altho, pas récursion directe utilisé), mais il retourne trully toutes les combinaisons (actuellement seulement paires, besoin d'étendre filterOut afin qu'il puisse retourner un tuple de deux listes, fera peu plus tard).

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 

peigne [1; 2; 3; 4] retournera: [[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, juste des combinaisons queue peu différente approche (sans utiliser la fonction bibliothèque)

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

La réponse acceptée est magnifique et rapidement compréhensible si vous êtes familier avec la récursivité des arbres. Puisque l'élégance était recherchée, ouvrir ce long fil dormant semble un peu inutile.

Cependant, une solution plus simple a été demandée. Les algorithmes itératifs me semblent parfois plus simples. En outre, la performance a été mentionnée comme un indicateur de qualité, et les processus itératifs sont parfois plus rapides que les processus récursifs.

Le code suivant est récursif et génère un processus itératif. Il faut un tiers du temps pour calculer des combinaisons de taille 12 à partir d'une liste de 24 éléments.

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

L'idée qui permet un processus itératif consiste à pré-calculer une carte du dernier élément choisi de la liste des éléments disponibles restants. Cette carte est stockée dans remainderAfter.

Le code n'est pas concis et ne correspond pas non plus à un compteur et une rime lyriques.

Answer 7

A naïf mise en œuvre en utilisant l'expression de séquence. Personnellement, je pense souvent que les expressions de séquence sont plus faciles à suivre que d'autres fonctions plus denses.

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

Méthode prise de Mathématiques discrètes et ses applications. Le résultat renvoie une liste ordonnée de combinaisons stockées dans des tableaux. Et l'index est basé sur 1.

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

Cette solution est simple et la fonction d'assistance coûte de la mémoire constante.