F # permutations

Cela dépend de ce que vous entendez par "mieux". J'envisagerais que cela soit légèrement plus élégant, mais cela peut être une question de goût: xxx

Ceci peut gérer des listes avec des éléments en double, bien qu'il aboutira à des permutations dupliquées.

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

Ça fonctionne comme suit: La fonction "Distribution" distribue un élément donné sur toutes les positions dans une liste, exemple: < / p> xxx

La fonction perms fonctionne (récursivement) comme suit: Distribuez la tête de la liste sur toutes les permutations de sa queue.

La fonction de distribution sera lente Pour les grandes listes, car il utilise beaucoup l'opérateur @, mais pour les listes de longueur raisonnable (<= 10), le code ci-dessus fonctionne bien.

Un avertissement: Si votre liste contient des doubles duplicats, le résultat contenir des permutations identiques. Par exemple: xxx

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érant des permutations avec un algorithme de tableau impératif sera (beaucoup) plus rapide, mais cet algorithme m'a bien servi dans la plupart des cas.

Voici la solution que j'ai donnée dans mon livre F # pour les scientifiques (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)

Voici une autre version à base de séquence, espérons-le plus lisible que la réponse votée. Cette version est similaire à la version de Jon en termes de logique, mais utilise des expressions de calcul au lieu des listes. La première fonction calcule toutes les méthodes d'insérer un élément x dans une liste l. La deuxième fonction calcule des permutations. Vous devriez être capable d'utiliser cela sur des listes plus importantes (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
      }

IMHO La meilleure solution devrait atténuer le fait que F # est une langue fonctionnelle de sorte que l'IMHO La solution devrait être aussi proche de la définition de ce que nous entendons la permanendation que possible. Donc, la permutation est une telle instance de la liste des choses où la tête de la liste est ajoutée en quelque sorte à la permutation du reste de la liste d'entrée. La solution Erlang montre que de manière jolie: xxx

prise froner le livre "Programmation Erlang"

Il y a un expertiper de compréhension de liste utilisée, dans la solution mentionnée ici par le compagnons de cheminement des fleurs Il y a une fonction d'assistance qui fait le travail similaire essentiellement, je voterais pour la solution sans aucune boucle visible, etc., une définition de fonction pure

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

où retirer code> est une fonction simple qui supprime un élément donné d'une liste p >

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

Je suis comme 11 ans de retard, mais toujours au cas où quelqu'un a besoin de permutations comme je l'ai récemment fait. Voici TRAY Version de permutation Func, je crois que c'est plus performant: xxx