Combinaisons d'éléments les plus élégantes en fa #

Question

Une autre question sur la mise en oeuvre la plus élégante et simple des combinaisons d’éléments en F #.

Il devrait renvoyer toutes les combinaisons d'éléments d'entrée (liste ou séquence). Le premier argument est le nombre d'éléments d'une combinaison.

Par exemple:

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

Answer 1

Une solution moins concise et plus rapide 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 existe une version plus concise de la réponse KV:

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

La réponse acceptée est magnifique et rapidement compréhensible si vous connaissez la récursivité des arbres. Depuis que l'élégance était recherchée, l'ouverture de 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, les performances ont été mentionnées comme un indicateur de qualité et les processus itératifs sont parfois plus rapides que les processus récursifs.

Le code suivant est tail récursif et génère un processus itératif. Il faut un tiers du temps nécessaire 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 est de pré-calculer une carte du dernier élément choisi sur une liste des éléments disponibles restants. Cette carte est stockée dans stayderAfter .

Le code n’est ni concis, ni conforme aux compteurs lyriques et aux comptines.

Answer 5

Une implémentation naïve utilisant une expression de séquence. Personnellement, j’ai souvent le sentiment 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 6

Méthode extraite de Mathématiques discrètes et applications . Le résultat renvoie une liste ordonnée de combinaisons stockées dans des tableaux. Et l’indice 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’aide coûte de la mémoire constante.

Answer 7

Ma solution est moins concise, moins efficace (même si aucune récursion directe n’est utilisée), mais elle renvoie réellement toutes les combinaisons (pour le moment, seules les paires, il faut étendre filterOut pour pouvoir renvoyer 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 8

Ok, juste des combinaisons de queue très différentes approches (sans utiliser la fonction de 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  ]