计算F#中的排列

Question

受这个问题和答案的启发,如何在F#中创建通用排列算法？谷歌没有给出任何有用的答案.

编辑:我在下面提供了我最好的答案,但我怀疑Tomas的更好(当然更短!)

Answer 1

你也可以写这样的东西:

let rec permutations list taken = 
  seq { if Set.count taken = List.length list then yield [] else
        for l in list do
          if not (Set.contains l taken) then 
            for perm in permutations list (Set.add l taken)  do
              yield l::perm }

'list'参数包含您要置换的所有数字,'taken'是包含已使用数字的集合.所有数字全部采用时,该函数返回空列表.否则,它迭代所有仍然可用的数字,获得剩余数字的所有可能排列(递归地使用'permutations')并在返回(l :: perm)之前将当前数字附加到每个数字.

要运行它,你会给它一个空集,因为在开头没有使用数字:

permutations [1;2;3] Set.empty;;

Answer 2

我喜欢这个实现(但不记得它的来源):

let rec insertions x = function
    | []             -> [[x]]
    | (y :: ys) as l -> (x::l)::(List.map (fun x -> y::x) (insertions x ys))

let rec permutations = function
    | []      -> seq [ [] ]
    | x :: xs -> Seq.concat (Seq.map (insertions x) (permutations xs))