F# 排列 [英] F# permutations

问题描述

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

I need to generate permutations on a given list. I managed to do it like this

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# 中实现这一点.

There are obvious issues with this code. For example, list elements must be unique. Also, this is more-less a same approach that I would use when generating straight forward implementation in any other language. Is there any better way to implement this in F#.

谢谢！

推荐答案

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

For permutations of small lists, I use the following code:

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"将给定元素分布到列表中的所有位置，例如:

It works as follows: the function "distrib" distributes a given element over all positions in a list, example:

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

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

The function perms works (recursively) as follows: distribute the head of the list over all permutations of its tail.

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

The distrib function will get slow for large lists, because it uses the @ operator a lot, but for lists of reasonable length (<=10), the code above works fine.

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

One warning: if your list contains duplicates, the result will contain identical permutations. For example:

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

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

The nice thing about this code is that it returns a sequence of permutations, instead of generating them all at once.

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

Of course, generating permutations with an imperative array-based algorithm will be (much) faster, but this algorithm has served me well in most cases.

这篇关于F# 排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！