Самые элегантные комбинации элементов в F #
-
10-07-2019 - |
Вопрос
Еще один вопрос о наиболее элегантной и простой реализации комбинаций элементов в F #.
Должен возвращать все комбинации входных элементов (список или последовательность). Первый аргумент - количество элементов в комбинации.
Например:
comb 2 [1;2;2;3];;
[[1;2]; [1;2]; [1;3]; [2;2]; [2;3]; [2;3]]
Решение
Одно менее сжатое и более быстрое решение, чем ssp:
let rec comb n l =
match n, l with
| 0, _ -> [[]]
| _, [] -> []
| k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs
Другие советы
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
Существует более краткая версия ответа 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)]
Принятый ответ великолепен и быстро понятен, если вы знакомы с рекурсией дерева. Поскольку требовалась элегантность, открытие этой длинной спящей нити кажется несколько ненужным. Р>
Однако было предложено более простое решение. Итерационные алгоритмы иногда кажутся мне проще. Кроме того, производительность упоминалась как показатель качества, и итерационные процессы иногда выполняются быстрее, чем рекурсивные. Р>
Следующий код является хвостовой рекурсией и генерирует итерационный процесс. Требуется треть времени для вычисления комбинаций размера 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
. Р>
Код не является кратким и не соответствует лирическому метру и рифме.
Реализация наивная с использованием выражения последовательности. Лично я часто чувствую, что выражения последовательности легче следовать, чем другие более плотные функции.
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)
Метод взят из Дискретной математики и ее приложений . Результат возвращает упорядоченный список комбинаций, хранящихся в массивах. И индекс основан на 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
[]
Это простое решение, а вспомогательная функция стоит постоянной памяти. Р>
Мое решение менее лаконично, менее эффективно (хотя и не используется прямая рекурсия), но оно полностью возвращает все комбинации (в настоящее время только пары, необходимо расширить 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]] р>
Хорошо, только хвостовые комбинации немного другой подход (без использования библиотечной функции)
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 ]