Las combinaciones de elementos más elegantes en F #

Question

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

Debería devolver todas las combinaciones de elementos de entrada (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 solución menos concisa y más rápida 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 una versión más concisa de la respuesta de 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 respuesta aceptada es magnífica y rápidamente comprensible si está familiarizado con la recursión de árboles. Como se buscaba la elegancia, abrir este largo hilo latente parece algo innecesario.

Sin embargo, se solicitó 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 recursivo de cola y genera un proceso iterativo. Se requiere un tercio de la cantidad de tiempo para calcular combinaciones de tamaño 12 a partir 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 que permite un proceso iterativo es calcular previamente un mapa del último elemento elegido en una lista de los elementos disponibles restantes. Este mapa se almacena en resto después de .

El código no es conciso, ni se ajusta al metro y la rima lírica.

Answer 5

Una implementación ingenua usando 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 6

Método tomado de Matemáticas discretas 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.

Answer 7

Mi solución es menos concisa, menos efectiva (aunque no se usa recursión directa) 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

comb [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 8

Ok, solo combinaciones de cola con un enfoque poco diferente (sin usar 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  ]