Большинство изящных комбинаций элементов в F#
Обратите внимание, что то, что необходимо сделать отступ 'тогда' и 'еще' в, 'действительно' блокируется, считается ошибкой многими. Это будет, вероятно, зафиксировано в Haskell' (главный Haskell), следующая версия спецификации Haskell.
5 ответов
Одно менее краткое и более быстрое решение, чем 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
Существует более продуманная версия ответа 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)]
Мое решение менее краткое, менее эффективное (альтернативно, без прямой рекурсии используется), но он действительно возвращает все комбинации (в настоящее время только пары, необходимо расширить 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 ]