Самые элегантные комбинации элементов в F #

Question

Еще один вопрос о наиболее элегантной и простой реализации комбинаций элементов в F #.

Должен возвращать все комбинации входных элементов (список или последовательность). Первый аргумент - количество элементов в комбинации.

Например:

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

Answer 1

Одно краткое и более быстрое решение, чем 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

Метод взят из Дискретная математика и ее приложения . Результат возвращает упорядоченный список комбинаций, хранящихся в массивах. И индекс на основе 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
        []

Это простое решение, а вспомогательная функция стоит постоянной памяти.

Answer 4

A naive реализация с использованием выражения последовательности. Лично я часто чувствую, что выражения последовательности легче следовать, чем другие более плотные функции.

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 5

Принятый ответ великолепен и быстро понятен, если вы знакомы с древовидной рекурсией. Поскольку требовалась элегантность, открытие этой длинной спящей нити кажется несколько ненужным.

Однако было предложено более простое решение. Итерационные алгоритмы иногда кажутся мне проще. Кроме того, производительность упоминалась как показатель качества, и итерационные процессы иногда выполняются быстрее, чем рекурсивные.

Следующий код является хвостовой рекурсией и генерирует итерационный процесс. Для вычисления комбинаций размера 12 из списка из 24 элементов требуется треть времени.

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

Идея, которая допускает итеративный процесс, состоит в том, чтобы предварительно вычислить карту последнего выбранного элемента в списке оставшихся доступных элементов. Эта карта хранится в remainderAfter.

Код не является кратким и не соответствует лирическому метру и рифме.

Answer 6

Существует более краткая версия ответа КВБ:

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 7

Хорошо, только хвостовые комбинации, немного другой подход (без использования библиотечной функции)

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 8

Мое решение менее лаконично, менее эффективно (хотя и не используется прямая рекурсия), но оно полностью возвращает все комбинации (в настоящее время только пары, необходимо расширить filterOut, чтобы оно могло возвращать кортеж из двух списков, что будет сделано чуть позже).

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] вернет: [[1; 2]; [1; 3]; [1; 4]; [2; 1]; [2; 3]; [2; 4]; [3; 1]; [3; 2]; [3; 4]; [4; 1]; [4; 2]; [4; 3]]