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屋!