Combinaciones más elegantes de elementos en F #

Question

Una pregunta más sobre la implementación más elegante y simple de las combinaciones de elementos en F #.

Debe devolver todas las combinaciones de elementos de entrada (ya sea Lista o Secuencia). El primer argumento es el número de elementos en una combinación.

Por ejemplo:

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

Answer 1

Una menos concisa y más rápido solución 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

Hay más versión consise de la respuesta 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

Mi solución es menos concisa, menos eficaz (Altho, sin la repetición directa se usa), pero realmente devuelve todas las combinaciones (actualmente solo pares, necesita extender filterOut para que pueda devolver una tupla de dos listas, lo hará poco después).

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 

peine [1; 2; 3; 4] devolverá: [[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

bien, combinaciones simplemente cola enfoque poco diferente (sin usar de la función de biblioteca)

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 respuesta aceptada es magnífico y rápidamente comprensible si está familiarizado con la recursividad de árbol. Desde que se buscó la elegancia, la apertura de este largo hilo inactivo parece algo innecesario.

Sin embargo, se pidió una solución más simple. Los algoritmos iterativos a veces me parecen más simples. Además, se mencionó el rendimiento como un indicador de calidad, y los procesos iterativos a veces son más rápidos que los recursivos.

El siguiente código es cola recursivo y genera un proceso iterativo. Se requiere un tercio de la cantidad de tiempo para calcular combinaciones de tamaño 12 de una lista de 24 elementos.

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

La idea de que permite un proceso iterativo es comprobar la validez de calcular un mapa del último elemento seleccionado a una lista de los elementos disponibles restantes. Este mapa se almacena en remainderAfter.

El código no es conciso, ni se ajusta al ritmo lírico ni a la rima.

Answer 7

A ingenuo implementación mediante la expresión de secuencia. Personalmente, a menudo siento que las expresiones de secuencia son más fáciles de seguir que otras funciones más densas.

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étodo tomado de Matemática Discreta y sus Aplicaciones. El resultado devuelve una lista ordenada de combinaciones almacenadas en matrices. Y el índice está basado en 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 
     [] 

Esta solución es simple y la función auxiliar cuesta memoria constante.