Die Berechnung Permutationen in F #

Question

Frage Inspired und Antwort , wie erstelle ich ein generischer Algorithmus Permutationen in F #? Google gibt nicht alle nützlichen Antworten.

EDIT: Ich biete meine beste Antwort unten, aber ich vermute, dass Tomas ist besser

(auf jeden Fall kürzer!)

Answer 1

Sie können auch so etwas schreiben:

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 }

Die ‚Liste‘ Argument enthält alle Zahlen, die Sie permutieren wollen und ‚genommen‘ ist eine Menge, die Zahlen, die bereits verwendet wird, enthält. Die Funktion gibt leere Liste, wenn alle Zahlen alle genommen. Ansonsten ist es iteriert alle Zahlen über die noch verfügbar sind, erhält alle möglichen Permutationen der restlichen Zahlen (rekursiv ‚Permutationen‘ verwenden) und fügt die aktuelle Nummer zu jedem von ihnen vor der Rückkehr (l :: perm).

Um dies zu laufen, werden Sie ihm eine leere Menge geben, da keine Zahlen am Anfang verwendet werden:

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

Answer 2

Ich mag diese Implementierung (kann aber die Quelle nicht erinnern):

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' Lösung ist recht elegant: es ist kurz, rein funktional, und faul. Ich denke, es ist sogar Schwanz-rekursiv sein kann. Außerdem erzeugt es Permutationen lexikografisch. Wir können jedoch die Leistung verbessern intern über eine dringend notwendige Lösungs zwei falten, während immer noch extern eine funktionelle Schnittstelle freigelegt wird.

Die Funktion permutations nimmt eine generische Sequenz e sowie eine allgemeine Vergleichsfunktion f : ('a -> 'a -> int) und träge ergibt lexikografisch unveränderlich Permutationen. Der Vergleich funktionelle ermöglicht es uns, Permutationen von Elementen zu erzeugen, die nicht notwendigerweise auch comparable so leicht rückgängig zu machen oder individuelle Anordnungen angeben.

Die innere Funktion permute ist der Imperativ Implementierung des Algorithmus beschrieben hier . Die Konvertierungsfunktion let comparer f = { new System.Collections.Generic.IComparer<'a> with member self.Compare(x,y) = f x y } ermöglicht es uns, die System.Array.Sort Überlastung zu verwenden, das tut in-Place-Unterbereich individuelle Art eine IComparer verwendet wird.

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' }

Jetzt Einfachheit halber haben wir die folgenden, wo let flip f x y = f y x:

let permutationsAsc e = permutations compare e
let permutationsDesc e = permutations (flip compare) e

Answer 4

Meine neueste beste Antwort

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

Die Permutationen Funktion funktioniert durch einen n-ary Baum Konstruktion alle möglichen Permutationen der Liste der ‚Dinge‘ darstellen übergeben, dann den Baum durchlaufen eine Liste von Listen zu konstruieren. Mit ‚Seq‘ dramatisch verbessert die Leistung, da es alles faul macht.

Der zweite Parameter der Permutationen Funktion ermöglicht es der Anrufer einen Filter für ‚Beschneidung‘ den Baum zu definieren, bevor die Pfade zu erzeugen (mein Beispiel unten sehen, wo ich keine führenden Nullen nicht will).

Einige Beispiel-Anwendung: Knoten < 'a> ist generisch, also können wir Permutationen tun ‚alles‘:

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] 

(Besonderer Dank geht an Tomas Petricek , die Kommentare sind willkommen)

Answer 5

Wenn Sie verschiedene permuations müssen (wenn der ursprüngliche Satz Duplikate hat), können Sie diese verwenden:

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
        }

Dies ist eine straight-forward Übersetzung von diese C # -Code. Ich bin offen für Vorschläge für eine weitere funktionelle Look-and-Feel.

Answer 6

Werfen Sie einen Blick auf diese:

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 7

Wenn Sie Permutationen mit Wiederholungen benötigen, ist dies die „durch das Buch“ Ansatz anstelle des Elements Vergleich List.indexed unter Verwendung von Elementen, um herauszufiltern, während eine Permutation konstruieren.

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