https://stackoverflow.com/questions/286427
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
受到问题和
解决方案
你也可以这样写：
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;;
其他提示
我喜欢这个实现（但不记得它的来源）：
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))
Tomas的解决方案非常优雅：它简短，功能纯粹，而且很懒惰。我认为它甚至可能是尾递归。此外，它按字典顺序产生排列。但是，我们可以在内部使用命令式解决方案将性能提高两倍，同时仍然在外部公开功能接口。
函数permutations采用通用序列e以及通用比较函数f : ('a -> 'a -> int)，并且以字典方式懒惰地产生不可变排列。比较功能允许我们生成元素的排列，这些元素不一定comparable，也可以轻松指定反向或自定义排序。
内部函数permute是此处所述算法的必要实现。转换函数let comparer f = { new System.Collections.Generic.IComparer<'a> with member self.Compare(x,y) = f x y }允许我们使用System.Array.Sort重载，使用IComparer进行就地子范围自定义排序。
let permutations f e =
///Advances (mutating) perm to the next lexical permutation.
let permute (perm:'a[]) (f: 'a->'a->int) (comparer:System.Collections.Generic.IComparer<'a>) : bool =
try
//Find the longest "tail" that is ordered in decreasing order ((s+1)..perm.Length-1).
//will throw an index out of bounds exception if perm is the last permuation,
//but will not corrupt perm.
let rec find i =
if (f perm.[i] perm.[i-1]) >= 0 then i-1
else find (i-1)
let s = find (perm.Length-1)
let s' = perm.[s]
//Change the number just before the tail (s') to the smallest number bigger than it in the tail (perm.[t]).
let rec find i imin =
if i = perm.Length then imin
elif (f perm.[i] s') > 0 && (f perm.[i] perm.[imin]) < 0 then find (i+1) i
else find (i+1) imin
let t = find (s+1) (s+1)
perm.[s] <- perm.[t]
perm.[t] <- s'
//Sort the tail in increasing order.
System.Array.Sort(perm, s+1, perm.Length - s - 1, comparer)
true
with
| _ -> false
//permuation sequence expression
let c = f |> comparer
let freeze arr = arr |> Array.copy |> Seq.readonly
seq { let e' = Seq.toArray e
yield freeze e'
while permute e' f c do
yield freeze e' }
为方便起见，我们在let flip f x y = f y x：
let permutationsAsc e = permutations compare e
let permutationsDesc e = permutations (flip compare) e
我最新的最佳答案
//mini-extension to List for removing 1 element from a list
module List =
let remove n lst = List.filter (fun x -> x <> n) lst
//Node type declared outside permutations function allows us to define a pruning filter
type Node<'a> =
| Branch of ('a * Node<'a> seq)
| Leaf of 'a
let permutations treefilter lst =
//Builds a tree representing all possible permutations
let rec nodeBuilder lst x = //x is the next element to use
match lst with //lst is all the remaining elements to be permuted
| [x] -> seq { yield Leaf(x) } //only x left in list -> we are at a leaf
| h -> //anything else left -> we are at a branch, recurse
let ilst = List.remove x lst //get new list without i, use this to build subnodes of branch
seq { yield Branch(x, Seq.map_concat (nodeBuilder ilst) ilst) }
//converts a tree to a list for each leafpath
let rec pathBuilder pth n = // pth is the accumulated path, n is the current node
match n with
| Leaf(i) -> seq { yield List.rev (i :: pth) } //path list is constructed from root to leaf, so have to reverse it
| Branch(i, nodes) -> Seq.map_concat (pathBuilder (i :: pth)) nodes
let nodes =
lst //using input list
|> Seq.map_concat (nodeBuilder lst) //build permutations tree
|> Seq.choose treefilter //prune tree if necessary
|> Seq.map_concat (pathBuilder []) //convert to seq of path lists
nodes
置换函数的工作原理是构造一个n元树，表示传入的“事物”列表的所有可能的排列，然后遍历树以构建列表列表。使用'Seq'可以显着提高性能，因为它会使一切变得懒惰。
排列函数的第二个参数允许调用者在生成路径之前定义用于“修剪”树的过滤器（请参阅下面的示例，其中我不需要任何前导零）。
一些示例用法：节点<！> lt;'a <！> gt;是通用的，所以我们可以做'任何'的排列：
let myfilter n = Some(n) //i.e., don't filter
permutations myfilter ['A';'B';'C';'D']
//in this case, I want to 'prune' leading zeros from my list before generating paths
let noLeadingZero n =
match n with
| Branch(0, _) -> None
| n -> Some(n)
//Curry myself an int-list permutations function with no leading zeros
let noLZperm = permutations noLeadingZero
noLZperm [0..9]
（特别感谢 Tomas Petricek ，欢迎任何评论）
如果您需要不同的permations（原始集合有重复），您可以使用：
let rec insertions pre c post =
seq {
if List.length post = 0 then
yield pre @ [c]
else
if List.forall (fun x->x<>c) post then
yield pre@[c]@post
yield! insertions (pre@[post.Head]) c post.Tail
}
let rec permutations l =
seq {
if List.length l = 1 then
yield l
else
let subperms = permutations l.Tail
for sub in subperms do
yield! insertions [] l.Head sub
}
这是这个 C＃代码。我愿意接受更实用的外观建议。
看一下这个：
http://fsharpcode.blogspot.com/2010/04/permutations.html
let length = Seq.length
let take = Seq.take
let skip = Seq.skip
let (++) = Seq.append
let concat = Seq.concat
let map = Seq.map
let (|Empty|Cons|) (xs:seq<'a>) : Choice<Unit, 'a * seq<'a>> =
if (Seq.isEmpty xs) then Empty else Cons(Seq.head xs, Seq.skip 1 xs)
let interleave x ys =
seq { for i in [0..length ys] ->
(take i ys) ++ seq [x] ++ (skip i ys) }
let rec permutations xs =
match xs with
| Empty -> seq [seq []]
| Cons(x,xs) -> concat(map (interleave x) (permutations xs))
如果你需要重复的排列，那就是书本上的<！> quot; <！>使用List.indexed而不是元素比较来构造置换时过滤掉元素。
let permutations s =
let rec perm perms carry rem =
match rem with
| [] -> carry::perms
| l ->
let li = List.indexed l
let permutations =
seq { for ci in li ->
let (i, c) = ci
(perm
perms
(c::carry)
(li |> List.filter (fun (index, _) -> i <> index) |> List.map (fun (_, char) -> char))) }
permutations |> Seq.fold List.append []
perm [] [] s
不隶属于 StackOverflow
