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」には、すでに使用されている数字が含まれるセットです。すべての数値が取得されると、関数は空のリストを返します。 それ以外の場合、まだ使用可能なすべての数値を反復処理し、残りの数値のすべての可能な順列を取得し（再帰的に「順列」を使用）、現在の数値を各数値に追加してから戻ります（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のソリューションは非常にエレガントです。それは短く、純粋に機能的で、怠laです。末尾再帰でさえあると思います。また、辞書順で順列を生成します。ただし、機能的なインターフェイスを外部に公開しながら、内部的に命令型ソリューションを使用してパフォーマンスを2倍に改善できます。
関数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」を使用すると、すべてが遅延するため、パフォーマンスが劇的に向上します。
permutations関数の2番目のパラメーターにより、呼び出し元は、パスを生成する前にツリーを「プルーニング」するためのフィルターを定義できます（先行ゼロが不要な次の例を参照してください）。
使用例：Node <！> 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]
個別の置換が必要な場合（元のセットに重複がある場合）、これを使用できます：
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
}
これは、 this 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;本の<< >> 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
