f#의 순열 계산

Question

이것에 영감을 받았습니다 의문 그리고 대답, f#에서 일반 순열 알고리즘을 어떻게 만들려면? Google은 이에 대한 유용한 답을 제공하지 않습니다.

편집 : 아래에서 가장 좋은 답변을 제공하지만 Tomas 's가 더 좋다고 생각합니다 (확실히 짧게!).

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 }

'목록'인수에는 순수 분출하려는 모든 숫자가 포함되어 있으며 '가져온'은 이미 사용 된 숫자를 포함하는 세트입니다. 함수는 모든 숫자가 모두 찍은 경우 빈 목록을 반환합니다. 그렇지 않으면, 여전히 사용 가능한 모든 숫자에 반복되고, 나머지 숫자 ( '순열'을 사용하여 재귀 적으로 재귀 적으로 순열)를 가져오고 (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의 솔루션은 매우 우아합니다. 짧고 순전히 기능적이며 게으르다. 나는 그것이 꼬리 추방적일 수도 있다고 생각합니다. 또한 부두로 순열을 생성합니다. 그러나 내부적으로 필수 솔루션을 사용하여 성능을 두 배나 향상시키면서 외부 적으로 기능 인터페이스를 노출시킬 수 있습니다.

함수 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 an을 사용하여 내부 하위 범위 사용자 정의 정렬을 수행하는 오버로드 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

순열 기능은 '사물'목록의 가능한 모든 순열을 나타내는 N-Ary 트리를 구성하여 트리를 통과하여 목록 목록을 구성함으로써 작동합니다. 'seq'를 사용하면 모든 것이 게으 르기 때문에 성능이 크게 향상됩니다.

순열 함수의 두 번째 매개 변수를 사용하면 발신자가 경로를 생성하기 전에 트리를 '가지 치기'에 대한 필터를 정의 할 수 있습니다 (아래의 예제를 참조하십시오.

일부 예제 사용 : 노드 < 'a>는 일반이므로'ally '의 순열을 할 수 있습니다.

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] 

(특별히 감사함 토마스 페트리 스크, 모든 의견을 환영합니다)

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

이것을 살펴보십시오 :

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