حساب التباديل في F #

Question

و <ل أ href = "https://stackoverflow.com/questions/283561/extracting-leaf-paths-from-n-ary-tree-in-f#283638"> الجواب ، كيف يمكنني إنشاء التباديل الخوارزمية العامة في F #؟ جوجل لا يعطي أي إجابات مفيدة لذلك.

وتحرير: I نقدم أفضل إجابة بلدي أدناه، ولكن أظن أن لتوماس هو أفضل

(بالتأكيد أقصر!)

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 }

وو"قائمة" حجة تحتوي على كافة الأرقام التي تريد بدل ترتيب كذا و "أخذ" عبارة عن مجموعة تحتوي على الأرقام المستخدمة بالفعل. ترجع الدالة قائمة فارغة عند كل الأرقام اتخاذ جميع. وإلا، فإنه بالتكرار عبر كافة الأرقام التي لا تزال متاحة، ويحصل كل التباديل الممكنة من الأرقام المتبقية (بشكل متكرر باستخدام 'التباديل') ويلحق العدد الحالي لكل واحد منهم قبل أن تعود (ل :: بيرم).

لتشغيل هذا، عليك أن تعطيه مجموعة فارغة، لأنه يتم استخدام أي أرقام في البداية:

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

وحل توماس "أنيقة جدا: انها قصيرة، وظيفية بحتة، وكسول. وأعتقد أنه قد يكون حتى الذيل العودية. أيضا، أنها تنتج التباديل lexicographically. ومع ذلك، يمكننا تحسين أداء شقين باستخدام محلول بد داخليا في حين لا يزال يعرض على واجهة وظيفية خارجيا.

ووpermutations وظيفة يأخذ تسلسل e عام وكذلك عام ظيفة مقارنة f : ('a -> 'a -> int) وبتكاسل ينتج التباديل ثابتة lexicographically. المقارنة وظيفية تسمح لنا لتوليد التباديل من العناصر التي لا يتم 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

Answer 4

وبلدي آخر أفضل إجابة

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

والتباديل وظيفة يعمل عن طريق بناء شجرة ن آرى تمثل جميع التبديلات الممكنة من قائمة "الأشياء" مرت في، ثم عبور شجرة لإنشاء قائمة من القوائم. باستخدام "تسلسل" بشكل كبير على تحسين الأداء لأنه يجعل كل شيء كسول.

والمعلمة الثانية من الدالة التباديل تسمح للطالب لتحديد مرشح ل"تشذيب" الشجرة قبل إنشاء مسارات (انظر بلدي على سبيل المثال أدناه، حيث لا أريد أي الأصفار البادئة).

وبعض المثال الاستعمال: عقدة < 'أ> هي عامة، حتى نتمكن من القيام التباديل' أي شيء ':

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] 

و(شكر خاص ل توماس Petricek ، أي تعليقات ترحب)

Answer 5

إذا كنت تحتاج permuations متميز (عندما المجموعة الأصلية لديها التكرارات)، يمكنك استخدام هذا:

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
        }

وهذا هو ترجمة مباشرة إلى الأمام من <لأ href = "https://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string/3178268#3178268" > هذا C # رمز. انا منفتح على اقتراحات لأكثر وظيفية نظرة وإحساس.

Answer 6

ونلقي نظرة على هذا واحد:

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

إذا كنت تحتاج التباديل مع التكرار، وهذا هو نهج "من قبل كتاب" باستخدام 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