Permutations F #

Question

J'ai besoin de générer des permutations sur une liste donnée. J'ai réussi à le faire comme ceci

let rec Permute (final, arr) = 
    if List.length arr > 0 then 
     for x in arr do 
      let n_final = final @ [x] 
      let rest = arr |> List.filter (fun a -> not (x = a)) 
      Permute (n_final, rest) 
    else 
     printfn "%A" final 

let DoPermute lst = 
    Permute ([], lst) 

DoPermute lst 

Il ya des problèmes évidents avec ce code. Par exemple, les éléments de liste doivent être uniques. Aussi, c'est plus ou moins la même approche que j'utiliserais pour générer une implémentation directe dans n'importe quelle autre langue. Y a-t-il une meilleure façon de l'implémenter en F #?

Merci!

Answer 1

Pour permutations de petites listes, j'utiliser le code suivant:

let distrib e L = 
    let rec aux pre post = 
     seq { 
      match post with 
      | [] -> yield (L @ [e]) 
      | h::t -> yield (List.rev pre @ [e] @ post) 
         yield! aux (h::pre) t 
     } 
    aux [] L 

let rec perms = function 
    | [] -> Seq.singleton [] 
    | h::t -> Seq.collect (distrib h) (perms t) 

Il fonctionne comme suit: la fonction « distrib » distribue un élément donné sur toutes les positions dans une liste, par exemple:

distrib 10 [1;2;3] --> [[10;1;2;3];[1;10;2;3];[1;2;10;3];[1;2;3;10]] 

La fonction perms fonctionne (récursivement) comme suit: répartir la tête de la liste sur toutes les permutations de sa queue. La fonction distrib sera lente pour les grandes listes, car elle utilise beaucoup l'opérateur @, mais pour les listes de longueur raisonnable (< = 10), le code ci-dessus fonctionne correctement. Un avertissement: si votre liste contient des doublons, le résultat contiendra des permutations identiques. Par exemple:

perms [1;1;3] = [[1;1;3]; [1;1;3]; [1;3;1]; [1;3;1]; [3;1;1]; [3;1;1]] 

La bonne chose à propos de ce code est qu'il renvoie une séquence de permutations, au lieu de les générer à la fois.

Bien sûr, générer des permutations avec un algorithme basé sur une matrice impérative sera (beaucoup) plus rapide, mais cet algorithme m'a bien servi dans la plupart des cas.

Answer 2

Cela dépend de ce que vous entendez par "mieux". Je considère que cela est un peu plus élégante, mais peut-être une question de goût:

(* get the list of possible heads + remaining elements *) 
let rec splitList = function 
| [x] -> [x,[]] 
| x::xs -> (x, xs) :: List.map (fun (y,l) -> y,x::l) (splitList xs) 

let rec permutations = function 
| [] -> [[]] 
| l -> 
    splitList l 
    |> List.collect (fun (x,rest) -> 
     (* permute remaining elements, then prepend head *) 
     permutations rest |> List.map (fun l -> x::l)) 

Cela peut gérer des listes avec des éléments en double, même si elle se traduira par des permutations dupliqués.

Answer 3

Voici la solution que j'ai donné dans mon livre F# for Scientists (page 166-167):

let rec distribute e = function 
    | [] -> [[e]] 
    | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs] 

let rec permute = function 
    | [] -> [[]] 
    | e::xs -> List.collect (distribute e) (permute xs) 

Answer 4

est ici une autre version basée sur la séquence, je l'espère plus lisible que la réponse voté. Cette version est similaire à la version de Jon en termes de logique, mais utilise des expressions de calcul au lieu de listes. La première fonction calcule toutes les façons d'insérer un élément x dans une liste l. La deuxième fonction calcule les permutations. Vous devriez pouvoir utiliser ceci sur des listes plus grandes (par exemple pour les recherches de force brute sur toutes les permutations d'un ensemble d'entrées).

let rec inserts x l = 
    seq { match l with 
     | [] -> yield [x] 
     | y::rest -> 
      yield x::l 
      for i in inserts x rest do 
       yield y::i 
     } 

let rec permutations l = 
    seq { match l with 
     | [] -> yield [] 
     | x::rest -> 
      for p in permutations rest do 
       yield! inserts x p 
     } 

Answer 5

à mon humble avis la meilleure solution devrait atténuer le fait que F # est un langage fonctionnel si IMHO la solution doit être aussi proche de la définition de ce que nous voulons dire qu'il ya permutation possible. Donc la permutation est une telle instance de liste de choses où la tête de la liste est en quelque sorte ajoutée à la permutation du reste de la liste d'entrée. La solution Erlang montre que, dans une jolie façon:

permutations([]) -> [[]]; 
permutations(L) -> [[H|T] H<- L, T <- permutations(L--[H]) ]. 

pris Fron la « programmation Erlang » livre

Il y a un opérateur de compréhension de la liste utilisée en solution mentionnée ici par le boursier stackoverflowers il y a une aide fonction qui fait le travail similaire au fond, je voterais pour la solution sans boucles visibles etc, juste pure définition de la fonction

Answer 6

Dans l'esprit de la suggestion de Cyrl, voici une version de compréhension de la séquence

let rec permsOf xs = 
    match xs with 
    | [] -> List.toSeq([[]]) 
    | _ -> seq{ for x in xs do 
       for xs' in permsOf (remove x xs) do 
       yield (x::xs')} 

où remove est une fonction simple qui supprime un élément donné dans une liste

let rec remove x xs = 
    match xs with [] -> [] | (x'::xs')-> if x=x' then xs' else x'::(remove x xs')