Cet article a fait l'objet d'une traduction automatique.

Série de tests

Combinaisons et permutations avec F#

James McCaffrey

Télécharger l'échantillon de code

Comprendre les combinaisons et les permutations est une capacité fondamentale en matière de test logiciel. Dans série de tests mois-ci cette je vous montrerai comment utiliser des combinaisons et des permutations à l'aide de code écrit dans le langage F #.

Une combinaison mathématique est un sous-ensemble d'éléments k sélectionnés à partir d'un ensemble de n éléments, dans laquelle ordre n'a pas d'importance. Pour ex suffisamment, si n = 5 et k = 2, tous les moyens possibles de sélectionner deux éléments à partir de cinq articles sont :

{0,1}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

Notez que je ne mentionnez pas la combinaison de {1} car il est considéré comme identique {0,1}. Par ailleurs, je have répertoriées les 10 combinaisons de cinq éléments sélectionné deux à la fois à l'aide de ce que l'on appelle un ordre lexicographique, où les valeurs dans chaque élément de combinaison sont répertoriées par ordre croissant.

Une permutation mathématique est tous les réorganisations possibles de n éléments. Par exemple, si n = 4, tout cela dans l'ordre lexicographique de permutations sont :

{0,1,2,3}, {0,1,3,2}, {0,2,1,3}, {0,2,3,1}, {0,3,1,2}, {0,3,2,1}, {1,0,2,3}, {1,0,3,2}, {1,2,0,3}, {1,2,3,0}, {1,3,0,2}, {1,3,2,0}, {2,0,1,3}, {2,0,3,1}, {2,1,0,3}, {2,1,3,0}, {2,3,0,1}, {2,3,1,0}, {3,0,1,2}, {3,0,2,1}, {3,1,0,2}, {3,1,2,0}, {3,2,0,1}, {3,2,1,0}

Lorsque vous travaillez avec des combinaisons et des permutations, deux fonctions importantes sont Choose (n, k) et Factorial(n). Vous êtes probablement familiarisé avec la fonction Factorial(n), qui est souvent abrégée n ! La fonction Factorial(n) renvoie le nombre total de permutations d'ordre n. Par exemple :

4! = 4 * 3 * 2 * 1 = 24.

La fonction Choose (n, k) renvoie le nombre total de combinaisons d'éléments k sélectionnés à partir de n éléments.

Choose(n,k) = n! / (k! * (n-k)!)

Par exemple :

Choose(5,2) = 5! / (2! * (5-2)!) = 5! / (2! * 3!) = 120 / 12 = 10.

Combinaisons et permutations font partie d'une zone d'étude généralement appelé COMBINATOIRE mathématiques ou combinatorics simplement en abrégé.

Un bon moyen vous permettant de voir où je suis se transforme en dans mois-ci ce consiste jeter un coup de œil sur la capture d'écran dans Figure 1. J'ai utilisé Windows PowerShell pour ordinateur hôte mon application de démonstration F #, mais je could a tout aussi facilement utilisés une invite de commandes. J'ai modifié mon script de démarrage de Windows PowerShell pour accéder automatiquement à l'emplacement de mon programme CombinatoricsDemo.exe.

Figure 1 Combinaisons et permutations avec F #

Les coulisses, la démonstration programme références et les appels dans une bibliothèque de code F# nommés CombinatoricsLib. La démonstration commence par répertorier toutes les combinaisons mathématiques de cinq éléments sélectionnés trois à la fois. Ensuite, il utilise une méthode d'assistance pour appliquer le dernier élément de combinaison {2,3,4}, à un tableau de chaînes {ant, bat, à la vache, chien, elk} pour {vache, chien, elk} — c'est-à-dire que les trois chaînes à partir du jeu d'origine situés à des valeurs d'index 2, 3 et 4.

Mon programme de démonstration se poursuit en informatique et en affichant la valeur de Choose(200,10), le nombre de méthodes de sélection d'éléments de 10 à partir d'un ensemble de 200 éléments où ordre n'a pas d'importance.

Ensuite, le code de démonstration calcule et affiche la valeur de Factorial(52), est le nombre total des moyens d'organiser les cartes dans un jeu standard de 52 cartes. Notez que le résultat est un très, très grand nombre. Comme je l'expliquerai, F # a la possibilité de travailler avec des valeurs d'entier arbitraire très élevé.

Mon programme de démonstration conclut en répertoriant toutes les permutations mathématiques d'ordre n = 3.

Dans les sections qui suivent, je décris en détail le code F # dans le module CombinatoricsLib et le code dans le programme de démonstration F # indiqué s'exécutant dans Figure 1. Tout au long du processus, je compare l'utilisation de F # avec d'autres langages comme Visual Basic et c# pour manipuler les combinaisons et les permutations.

Cet article suppose que débutants à intermédiaires expérience avec un langage .NET tel que c# et une connaissance élémentaire de F #. Mais même si vous êtes totalement nouveau pour F #, vous devez pouvoir suivre mes explications sans trop difficulté.

La bibliothèque F # CombinatoricsLib

Pour créer ma bibliothèque combinatorics, j'ai utilisé la version bêta 2 de Visual Studio 2010, qui possède le langage F # et les outils intégrés. J'attends le F # code que je présente ici fonctionne avec la version finale de Visual Studio 2010 sans modification significative. Si vous utilisez une version antérieure de Visual Studio, vous pouvez trouver les outils F # sur le F # Centre pour développeurs Microsoft (MSDN.Microsoft.com/FSharp). Avec le langage F #, Visual Studio 2010 est fourni avec Microsoft .NET Framework 4, qui utilise ma bibliothèque.

J'ai créé ma bibliothèque en lancer Visual Studio 2010 et en sélectionnant fichier | nouveau | projet. Dans la boîte de dialogue Nouveau projet, j'ai sélectionné le modèle F# Library et nommé ma bibliothèque CombinatoricsLib. La structure générale de mon CombinatoricsLib est répertoriée dans Figure 2.

Figure 2 Structure de F # CombinatoricsLib

module Module1

open System
open System.Numerics // BigInteger class

type Combination(n : int, k : int, a : int[]) = 
  // primary constructor code
  new(n : int, k : int) =
    ...
  member this.IsLast() : bool =
    ... 
  member this.Successor() : Combination =
    ... 
  member this.ApplyTo(a : string[]) : string[] =
    ...
  override this.ToString() : string =
    ... 
  static member Choose(n : int, k : int) : BigInteger =
    ...
  static member Factorial(n : int) : BigInteger =
    ...  
// end type Combination

type Permutation(n : int, a : int[]) =
  // primary constructor code
  new(n : int) =
    ...
  override this.ToString() : string =
    ...
  member this.Successor() : Permutation =
    ... 
  member this.ApplyTo(a : string[]) : string[] =
    ...
  member this.IsLast() : bool =
// end type Permutation

Le code de bibliothèque commence par le code généré par Visual Studio qui nomme ma bibliothèque Module1. J'ai utilisé ce nom par défaut plutôt nondescript au lieu de modifier un nom plus explicite pour que la syntaxe permettant d'accéder à la bibliothèque ressort plus loin dans cet article.

Ensuite, j'ai ajouté deux F # ouvrir les instructions pour l'espace de noms System niveau supérieur et le nouvel espace de noms System.Numerics ; je CAN accéder aux classes dans ces espaces de noms sans qualifier complètement les noms de classe. L'espace de noms System.Numerics fait partie du .NET Framework 4 et contient une définition BigInteger qui permet de travailler avec des valeurs entières arbitrairement volumineux.

Définition d'un type en F # diffère de la définition d'une classe c# conceptuellement équivalente. La définition de type a une signature qui contient les arguments d'entrée pour le constructeur de type principal :

type Combination(n : int, k : int, a : int[]) =

Cette signature, “ je suis définissant un type nommé combiné possède un constructeur principal qui accepte les arguments int n (nombre total d'éléments) et k (taille de sous-ensemble) et un tableau d'entiers un qui spécifie les valeurs de combinaison individuelles, telles que {0,1,4}. ”

F # types peuvent avoir des constructeurs secondaires facultatifs, tel que celui figurant dans Figure 2:

new(n : int, k : int) =

Notez que les constructeurs secondaires utiliser le mot clé new explicite par opposition aux constructeurs de type principal. Ce constructeur secondaire accepte des valeurs uniquement pour n et k. Avec d'autres langages de programmation tel que c#, on probablement définit le constructeur plus simple que le constructeur primaire, c'est-à-dire, avant les constructeurs qui acceptent des arguments. Mais comme vous le verrez en F #, pour les types de plusieurs constructeurs, il est recommandé de créer un type de manière à ce que le constructeur principal est celui pour lequel la plupart des paramètres. La structure de mon type de combinaison continue avec trois fonctions membres :

member this.IsLast() : bool =
  ... 
member this.Successor() : Combination =
  ... 
member this.ApplyTo(a : string[]) : string[] =
  ...

Le mot clé this lie méthodes membres visibles publiquement à un code appelant externe. La fonction IsLast retourne true si l'objet de combinaison associé est le dernier élément dans l'ordre lexicographique, comme {2,3,4} pour n = 5 et k = 3, comme dans Figure 1.

La fonction Successor renvoie l'élément de combinaison suivant dans l'ordre lexicographique dans l'élément actuel.

La fonction ApplyTo accepte un tableau de chaînes et retourne un tableau de chaînes qui correspond à l'élément de combinaison en cours.

Ma fonction de membre de type suivante permet d'afficher un élément de combinaison :

override this.ToString() : string =

J'utilise le mot-clé override pour distinguer ma fonction personnalisée de ToString de la méthode ToString de base. Étant donné que F # est un langage .NET, tous les objets héritent à partir d'un objet de base commun qui possède une méthode ToString. Notez que même si la fonction substituée ToString a portée publique, je n'utilise pas le mot clé de membre.

Les fonctions deux derniers membres du type de combinaison de définissent les fonctions Choose et Factorial :

static member Choose(n : int, k : int) : BigInteger =  ...
static member Factorial(n : int) : BigInteger =  ...

Les deux fonctions sont statiques, ce qui signifie que les fonctions sont associées et appelées directement à partir du contexte de type de combinaison plutôt qu'une instance particulière d'un objet de combinaison. Les deux fonctions renvoient type BigInteger, défini dans namespace System.Numerics, qui sont directement consultables par défaut par code F #.

En plus un type de combinaison, je définir un type de permutation comme indiqué dans la liste dans Figure 2.

La mise en oeuvre de la bibliothèque F # Combinatorics

Maintenant let’s passez en revue les détails de la mise en oeuvre de la bibliothèque CombinatoricsLib. Le constructeur primaire combinaison commence :

type Combination(n : int, k : int, a : int[]) = 
  do if n < 0 || k < 0 then failwith 
    "Negative argument in Combination ctor"
  do if n < k then failwith 
    "Subset size k is larger than n in Combination"

Il est intéressant de noter que, pour effectuer la validation d'argument d'entrée dans un constructeur primaire, vous devez utiliser le mot clé, qui indique une action, au lieu de la valeur par défaut, une valeur qui est généralement assumée par les langages fonctionnels tels que F #. Le mot clé failwith lève une exception, ce qui peut être interceptée par le code appelant.

Ensuite, j'ai configuré les membres privés de type combinaison :

let n : int = n // private
let k : int = k
let data = 
  [| for i = 0 to a.Length-1 do yield a.[i] |]

Le mot clé let lie les valeurs aux membres privés. Notez que je CAN utilise minuscules n et k comme les deux paramètres d'entrée et en tant que champs privés. Cela semble un peu maladroite et donc dans la plupart des cas je peux utiliser notation en majuscules pour les paramètres ou les membres privés.

Copie les valeurs à partir du tableau argument d'entrée un dans le type de données de champ utilisent un idiome F # standard. Le délimiteurs [|. . |] indiquent un tableau mutable. Le constructeur de combinaison secondaire crée un objet de combinaison initial et est défini comme :

new(n : int, k : int) = 
  do if n < 0 || k < 0 then failwith 
    "Negative argument in Combination ctor"
  do if n < k then failwith 
    "Subset size k is larger than n in Combination"
  let starters = [| for i in 0..k-1 -> i |] 
  new Combination(n,k,starters)

En F #, les constructeurs secondaires doivent appeler le constructeur primaire. Donc je définir un tableau int nommé venus, avec les valeurs 0 et 1 k et passez-lui avec n et k au constructeur primaire. Ce mécanisme F # est la raison pour laquelle il est conseillé de définir n'importe quel constructeur principal en tant que le constructeur avec la plupart des paramètres.

La fonction membre IsLast est définie comme suit :

member this.IsLast() : bool =
  if data.[0] = n-k then true
  else false

In Figure 1, notez que seul le dernier élément dans une liste de toutes les combinaisons a la valeur n-k, situé dans la première position du tableau. F # n'utilise pas un mot-clé de retour explicite comme la plupart des langues ; retour implicite est la dernière valeur dans une fonction, dans ce cas true ou false. Le = jeton vérifie l'égalité en F # et n'est pas un opérateur d'assignation. La fonction Combination.Successor est :

member this.Successor() : Combination =
  // copy input to temp array
  let temp = [| for i in 0..k-1 -> data.[i] |] 
  // find "x" - right-most index to change 
  let mutable x = k-1 
  while x > 0 && temp.[x] = n - k + x do 
    x <- x - 1
  temp.[x] <- temp.[x] + 1 // increment value at x
  // increment all values to the right of x
  for j = x to k-2 do 
    temp.[j+1] <- temp.[j] + 1
  // use primary ctor
  let result = new Combination(n, k, temp) 
  result

Je commence en copiant les valeurs du contexte en cours de l'objet combiné dans un tableau mutable nommé temp. Ensuite, je définis une variable d'index nommée x et positionnez-le à la fin du tableau temporaire. Je must utilisez le mot-clé mutable afin que je CAN décrémenter cette variable d'index dans la mesure où, par défaut, la plupart des variables en F # sont immuables. J'utilise le <-opérateur d'assignation.

Une fois que je localiser l'index clé de l'objet en cours de la combinaison, j'incrémente cette valeur et toutes les valeurs à droite de l'index de clé. Puis je transmets tableau temporaire, ce qui a la valeur de l'élément de combinaison successeur, dans le constructeur primaire maintenant et renvoyer l'objet nouvellement créé.

Notez que je ne retournent pas null lorsque je suis au dernier élément de combinaison — en F #, il est considéré un style médiocre pour ce faire. Le code que je présente dans cet article utilise un style qui n'est pas très F #-Ier. F # experts probablement utiliser une approche récursive, mais étant donné que je suis en supposant que vous ne connaissez pas F #, je souhaitais que mon code F # comme familier que possible.

L'autre manière d'écrire une fonction Successor consiste à implémenter l'interface IEnumerable de .NET.

La fonction ApplyTo permet de mapper un élément de combinaison sur un jeu de valeurs de chaîne :

member this.ApplyTo(a : string[]) : string[] =
  if a.Length <> n then failwith 
    "Invalid array size in ApplyTo()"
  // array of int
  let result = Array.zeroCreate k
  for i = 0 to k-1 do
    // bind to array of string
    result.[i] <- a.[data.[i]]
  result

Lors de l'exécution argument d'entrée de contrôles dans une fonction membre, je n'ai pas besoin d'utiliser le mot-clé nécessaires dans les constructeurs de type. La méthode Array.zeroCreate statique crée un tableau entier initialisé à toutes les valeurs 0 comme prévu. La fonction ApplyTo est facile, car la plage de valeurs dans une combinaison mathématique avec sous-ensemble dimensionner k (0..k - 1) est exactement le même que les index de n'importe quel tableau .NET de taille k.

La fonction de membre substituée ToString crée simplement une chaîne composée de valeurs de l'objet de contexte :

override this.ToString() : string =
  let mutable s : string = "^ "
  for i in 0..k-1 do
    s <- s + data.[i].ToString() + " "
  s <- s + "^"
  s

J'ai décidé de délimiter mes éléments de combinaison avec le ^ (exponentiation) caractère, ce qui démarre avec la lettre c et pour délimiter mes éléments de permutation à l'aide le caractère % (%), qui commence par p, pour m'aider à déterminer si une chaîne de chiffres représente une combinaison ou d'un objet de permutation.

La fonction Choose statique est codée comme dans Figure 3. 

Figure 3 La fonction choisir

static member Choose(n : int, k : int) : BigInteger =
  if n < 0 || k < 0 then failwith 
    "Negative argument in Choose()"
  if n < k then failwith 
    "Subset size k is larger than n in Choose()"
  let (delta, iMax) =
    if k < n-k then
      (n-k, k)
    else
      (k, n-k)
  let mutable answer : BigInteger = 
    bigint delta + bigint 1 
  for i = 2 to iMax do
    answer <- (answer * (bigint delta + bigint i )) 
      / bigint i
  answer

Au lieu de l'informatique choisir à partir de la définition décrite plus haut dans cet article, j'utilise deux optimisations. Tout d'abord, j'utiliser le fait que Choose (n, k) = choisir (n, n-k). Par exemple Choose(9,6) = Choose(9,3). Deuxièmement, plutôt que de factorielles distinct trois compute, chacun d'entre eux peut être très volumineux, je calculer une série de produits partielles. Pour convertir explicitement les valeurs de type int en type BigInteger, j'utilise la fonction de type bigint F # intégrée.

L'implémentation du type de permutation est très similaire à l'implémentation du type de combinaison. Vous pouvez obtenir le code source complete pour la bibliothèque CombinationLib à partir du site Microsoft Code Gallery Web à code.msdn.microsoft.com.

À l'aide de la CombinatoricsLib

Dans cette section, j'explique comment appeler la fonction de la bibliothèque CombinatoricsLib pour produire l'exécution montre la capture d'écran dans Figure 1. Je commencer par lancer Visual Studio 2010 et comment créer un nouveau projet d'application F # nommé CombinatoricsDemo. Le programme entier est répertorié dans Figure 4.

Figure 4 À l'aide de la CobinatoricsLib

open System
open Module1 // the Combinatorics Lib

try

  printfn "\nBegin combinations and permutations with F# demo\n"
  printfn "All combinations of 5 items 3 at a time in lexicographical order are: \n"
  let mutable c = new Combination(5,3)
  printfn "%A" c // print initial combination

  // objects cannot be null in F# so use an explicit method
  while c.IsLast() = false do 
    c <- c.Successor()
    printfn "%A" c
   
  printf "\nThe last combination applied to array [| \"ant\"; \"bat\"; \"cow\"; \"dog\"; \"elk\" |] is: \n"
  let animals = [| "ant"; "bat"; "cow"; "dog"; "elk" |]
  //let result =  c.ApplyTo(animals)
  let result = animals |> c.ApplyTo
  printfn "%A" result

  printfn "\nThe number of ways to Choose 200 items 10 at a time = Choose(200,10) ="
  let Choose_200_10 = Combination.Choose(200,10).ToString("000,000")
  printfn "%s" Choose_200_10

  printfn "\nThe number of ways to arrange 52 cards = 52! = "
  let Factorial_52 = Combination.Factorial(52).ToString("000,000")
  printfn "%s" Factorial_52

  printfn "\nAll permutations of 3 items in lexicographical order are: \n"
  let mutable p = new Permutation(3)
  printfn "%A" p // print initial permutation
  while p.IsLast() = false do
    p <- p.Successor() 
    printfn "%A" p
      
  printfn "\nEnd demo\n"
  Console.ReadLine() |> ignore

with
  | Failure(errorMsg) -> printfn "Fatal error: %s" errorMsg

// end program

Avant d'écrire de code, j'ai cliqué avec le bouton droit sur le nom du projet dans la fenêtre Explorateur de solutions de Visual Studio et sélectionné l'option Ajouter une référence dans le menu contextuel. Puis, j'ai sélectionné l'onglet Parcourir et que vous avez accédé à l'assembly CombinatoricsLib.dll.

Je commence le code de programme de démonstration par l'ajout d'instructions ouvertes dans les assemblys système et Module1. N'oubliez pas que le nom du module de la CombinatorcsLib est Module1. J'encapsule toutes les instructions de programme dans un bloc try / avec bloc de capturer et de gérer des exceptions. J'instancie un objet de combinaison à l'aide du constructeur secondaire pour rendre un c objet combinaison mathématique initiale de cinq éléments prises trois à la fois : {0,1,2}. J'utilise le claire F # %A spécificateur de format, qui prescrit à F # pour inférer l'impression de mon objet combiné. J'ai could également ont utilisé le format de la chaîne %s.

Ensuite, j'utilise F # lorsexécuter une boucle pour parcourir et afficher tous les éléments Combination(5,3) 10. À ce stade, le c objet combiné est le dernier élément et j'appeler la fonction ApplyTo mapper cette combinaison sur un tableau de chaînes.

Notez que j'appelle les fonctions Factorial et de choisir à partir du contexte de type de combinaison plutôt que l'objet de combinaison c. Après avoir appelé le code du type de permutation de manière similaire, le programme de démonstration conclut en suspension pour l'entrée d'utilisateur avec la méthode console.ReadLine, où je transférer la valeur de retour à l'objet intégré ignore. Je gérer les exceptions dans le bloc, en affichant simplement le message d'erreur exception.

Parallèlement à appeler une bibliothèque F# à partir d'un programme F #, comme je 've simplement, vous pouvez appeler une bibliothèque F# à partir de n'importe quel langage compatible .NET. En outre, Visual Studio vous permet d'utiliser la pratique F # interactive fenêtre pour effectuer des appels ad hoc, comme dans Figure 5.

Figure 5 Utilisation interactive d'une bibliothèque F #

Dans la F # fenêtre interactive du bas de l'écran, j'ajoutez une référence à l'assembly CombinatoricsLib en tapant :

#r @"C:\(path)\CombinatoricsLib.dll";;

Dans ce cas # r signifie ajouter une référence, et; met fin à une instruction F # interactive. Maintenant je CAN interactivement appelle les fonctions de la bibliothèque. Parfait !

Dans mon avis, il existe plusieurs avantages et inconvénients à l'aide de F #. Côté négatif, j'ai trouvé que la courbe d'apprentissage pour F # était beaucoup plus raide que prévu. Écrit dans un style fonctionnel était un changement de paradigme importante pour moi. Beaucoup plus ainsi que d'autres langages, F # est aussi plusieurs méthodes de codage d'une tâche particulière, qui ont conduit me sentir uneasy sur si aucun code F # j'ai écrit a été écrit de façon optimale.

Toutefois, dans mon cas au moins, je suis les avantages de la formation F # définitivement l'emportent sur les coûts. Lorsque parlé à expérimentés F # codeurs, la plupart m'a dit que dans de nombreux cas, même s'il existe en fait plusieurs manières pour coder une tâche, l'approche adoptée est plus une question de préférence personnelle que l'efficacité technique. En outre, codage paradigmes (tels qu'immuabilité par défaut) et de résolution avec une syntaxe F # m'as donné ce que je feutres a été certains approfondie de bon de codage dans des procédures de langages tels que c#.

Dr. James McCaffrey *travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant sur le Microsoft Redmond, Washington, campus. Il a travaillé sur plusieurs produits Microsoft, dont Internet Explorer et MSN Search. Dr McCarthy est l'auteur de “ .NET Test Automation Recipes ” (Apress, 2006). Vous pouvez le contacter à jammc@microsoft.com.                     *

Je remercie les experts techniques suivants d'avoir relu cet article :  Brian McNamara, Paul Newson et Matthew Podwysocki