F#中最优雅的元素组合

Question

关于在F#中实现元素组合的最优雅和简单的方式，我有一个问题。

它应该返回输入元素（无论是列表还是序列）的所有组合。第一个参数是组合中元素的数量。

例如：

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

- The_Ghost

---

稍微相关的问题：https://dev59.com/CXVC5IYBdhLWcg3wdw65 - Benjol

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

- The_Ghost

---

有人能比那个解决方案更简单地写吗？ - The_Ghost

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

- kvb

---

目前最快的解决方案，但不够简洁。 - The_Ghost

在C#中它看起来非常丑陋。public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> xs,int n) { if(n == 0){ return new []{Enumerable.Empty<T>()}; }else if(!xs.Any()){ return Enumerable.Empty<IEnumerable<T>>(); }else{ var head = xs.First(); var tail = xs.Skip(1); var useX = (Combinations(tail,n-1)).Select(l => (new[]{head}).Concat(l)); var noX = Combinations(tail,n); return useX.Concat(noX); } } - Rezo Megrelidze

Answer 3

使用序列表达式的天真实现。个人认为，序列表达式比其他更密集的函数更易于理解。

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)

- user483036

Answer 4

接受的答案非常漂亮，如果您熟悉树递归，那么很快就能理解。由于追求优雅，因此似乎没有必要打开这个长时间未使用的线程。

但是，需要一个更简单的解决方案。对我来说，迭代算法有时似乎更简单。此外，性能被提到作为质量的指标，迭代过程有时比递归过程更快。

以下代码是尾递归的，并生成迭代过程。相较于从24个元素的列表中计算大小为12的组合，它只需要三分之一的时间。

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中。

代码不够简洁，也不符合抒情韵律和押韵。

- Bill Johnson

Answer 5

有一份更简洁的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)]

- ssp

Answer 6

方法取自《离散数学及其应用》。 结果返回存储在数组中的有序组合列表。 索引从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
        []

这个解决方案很简单，帮助函数的内存消耗是恒定的。

- Aria Ax

Answer 7

我的解决方案不太简洁，也不够有效（虽然没有直接使用递归），但它确实可以返回所有的组合（目前仅限于一对，需要扩展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]]

- Ray

---

这个解决方案不正确。它没有返回组合，而只返回元素对。 - The_Ghost

这是所有可能的组合，不仅仅是尾组合。comb [1;2;3] 表示将 1 加到 [2;3] 中的每个数字，将 2 加到 [1;3] 中的每个数字，将 3 加到 [1;2] 中的每个数字。 - Ray

组合 3 [1..4];; val it : int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 4]; [2; 3; 4]]当元素更多时，它不应该返回一对，而是三元组（n=3）。 - The_Ghost

Answer 8

好的，只是尾部组合有一些不同的方法（不使用库函数）

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  ]

- Ray