F# 排列

Question

我需要在给定的列表上生成排列。我设法这样做

let rec Permute (final, arr) = 
    if List.length arr > 0 then
        for x in arr do
            let n_final = final @ [x]
            let rest = arr |> List.filter (fun a -> not (x = a))
            Permute (n_final, rest)
    else
        printfn "%A" final

let DoPermute lst  = 
    Permute ([], lst)

DoPermute lst

这段代码有明显的问题。例如，列表元素必须是唯一的。此外，这与我在以任何其他语言生成直接实现时使用的方法相同。有没有更好的方法在 F# 中实现这一点。

谢谢!

Answer 1

对于小列表的排列，我使用以下代码:

let distrib e L =
    let rec aux pre post = 
        seq {
            match post with
            | [] -> yield (L @ [e])
            | h::t -> yield (List.rev pre @ [e] @ post)
                      yield! aux (h::pre) t 
        }
    aux [] L

let rec perms = function 
    | [] -> Seq.singleton []
    | h::t -> Seq.collect (distrib h) (perms t)

它的工作原理如下:函数“distrib”将给定元素分布在列表中的所有位置，例如:

distrib 10 [1;2;3] --> [[10;1;2;3];[1;10;2;3];[1;2;10;3];[1;2;3;10]]

函数 perms 的工作方式(递归)如下:将列表的头部分布在其尾部的所有排列上。

distrib 函数对于大列表会变慢，因为它经常使用@ 运算符，但是对于合理长度(<=10)的列表，上面的代码可以正常工作。

一个警告:如果您的列表包含重复项，结果将包含相同的排列。例如:

perms [1;1;3] = [[1;1;3]; [1;1;3]; [1;3;1]; [1;3;1]; [3;1;1]; [3;1;1]]

这段代码的好处在于它返回一个排列序列，而不是一次生成它们。

当然，使用基于数组的命令式算法生成排列会(快得多)快，但这种算法在大多数情况下对我很有用。