A maioria das combinações elegantes de elementos em F #

Question

Mais uma pergunta sobre a maioria implementação elegante e simples de combinações de elementos em F #.

Ele deve retornar todas as combinações de elementos de entrada (lista ou sequência). O primeiro argumento é o número de elementos em uma combinação.

Por exemplo:

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

Answer 1

Um menos concisa e solução mais rápido do 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

Há mais versão concisa da resposta 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

A resposta aceita é lindo e rapidamente compreensível se você está familiarizado com recursão árvore. Desde elegância foi procurado, abrindo esta discussão há muito adormecido parece um pouco desnecessário.

No entanto, uma solução mais simples foi solicitado. algoritmos iterativos às vezes parecem mais simples para mim. Além disso, o desempenho foi mencionado como um indicador de qualidade e processos iterativos são, por vezes mais rápido do que aqueles recursiva.

O código a seguir é rabo recursiva e gera um processo iterativo. Exige um terço da quantidade de tempo para combinações de computação de tamanho 12 a partir de uma 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 [[]]

A idéia de que permite um processo iterativo é pré-computar um mapa do último elemento escolhido para uma lista dos restantes elementos disponíveis. Este mapa é armazenado em remainderAfter.

O código não é conciso, nem em conformidade com medidor de lírico e rima.

Answer 5

R ingénuo execução usando expressão de sequência. Pessoalmente, eu muitas vezes se sentem expressões de seqüência são mais fáceis de seguir do que outras funções mais 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 tirado de Matemática Discreta e suas aplicações . O resultado retorna uma lista ordenada de combinações armazenadas em arrays. E o índice é 1-base.

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 solução é simples e função auxiliar custa memória constante.

Answer 7

A minha solução é menos conciso, menos eficaz (altho, nenhuma recursão direta empregada), mas trully retorna todas as combinações (atualmente apenas pares, necessidade de estender filterOut para que ele possa retornar uma tupla de duas listas, fará pouco mais tarde).

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

pente [1; 2; 3; 4] retornará: [[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, combinações apenas cauda pequena abordagem diferente (sem usar da função 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  ]