algorithm - F# での順列の計算

Question

この質問と回答に触発されて、F# で一般的な順列アルゴリズムを作成するにはどうすればよいですか? Google はこれに対して有用な回答を提供していません。

編集：以下に私の最良の答えを提供しますが、トーマスの方が優れていると思います（確かに短いです！）

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

Answer 3

Tomas のソリューションは非常に洗練されています。短く、純粋に機能的で、怠惰です。末尾再帰でさえあると思います。また、辞書順で順列を生成します。ただし、機能的なインターフェイスを外部に公開しながら、内部で命令型ソリューションを使用してパフォーマンスを 2 倍向上させることができます。

この関数は、一般的な比較関数と同様にpermutations一般的なシーケンスを取り、不変の順列を辞書的に遅延して生成します。比較関数を使用すると、必ずしも必要ではない要素の順列を生成したり、逆順またはカスタム順序を簡単に指定したりできます。ef : ('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.SortIComparer

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

Answer 4

これを見てください：

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

Answer 5

個別の順列が必要な場合 (元のセットに重複がある場合)、これを使用できます。

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# コードからの単純な翻訳です。より機能的なルック アンド フィールの提案を歓迎します。

Answer 6

私の最近のベストアンサー

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

permutations 関数は、渡された「もの」のリストのすべての可能な順列を表す n-ary ツリーを構築し、ツリーをトラバースしてリストのリストを構築することによって機能します。「Seq」を使用すると、すべてが遅延するため、パフォーマンスが劇的に向上します。

permutations 関数の 2 番目のパラメーターを使用すると、呼び出し元は、パスを生成する前にツリーを「剪定」するためのフィルターを定義できます (以下の例を参照してください。先行ゼロは必要ありません)。

いくつかの使用例: Node<'a> はジェネリックであるため、「何でも」の順列を実行できます。

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に感謝します。コメントは歓迎します)