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

这是我在F#科学家的书中给出的解决方案(第166-167页):

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let rec permute = function
  | [] -> [[]]
  | e::xs -> List.collect (distribute e) (permute xs)

Answer 2

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

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]]

这段代码的好处是它返回一系列排列,而不是一次性生成所有排列.

当然,使用命令式基于阵列的算法生成排列(更快)会更快,但是这种算法在大多数情况下都很适合我.

Answer 3

这是另一个基于序列的版本，希望比投票的答案更具可读性。这个版本在逻辑上与 Jon 的版本类似，但使用计算表达式而不是列表。第一个函数计算在列表 l 中插入元素 x 的所有方法。第二个函数计算排列。您应该能够在更大的列表上使用它（例如，对一组输入的所有排列进行强力搜索）。

let rec inserts x l =
  seq { match l with
        | [] -> yield [x]
        | y::rest ->
            yield x::l
            for i in inserts x rest do
              yield y::i
      }

let rec permutations l =
  seq { match l with
        | [] -> yield []
        | x::rest ->
            for p in permutations rest do
              yield! inserts x p
      }