Este artículo proviene de un motor de traducción automática.

Ejecución de pruebas

Combinaciones y permutaciones con F#

James McCaffrey

Descargar el código de ejemplo

Permutaciones y combinaciones de comprensión es una habilidad fundamental en las pruebas de software. En la columna Test Run de este mes mostraré cómo trabajar con combinaciones y las permutaciones utilizando código escrito en el nuevo lenguaje de F #.

Una combinación matemática es un subconjunto de k elementos seleccionados de un conjunto de n elementos, orden no importa. Para un amplio ex, si n = 5 y k = 2, todos los posibles maneras de seleccionar dos elementos de cinco elementos son:

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

Observe que no enumere la combinación de {1} porque se considera igual que {0,1}. Asimismo, he mencionados los 10 combinaciones de cinco elementos seleccionado dos a la vez mediante lo que se denomina orden lexicográfica, donde los valores en cada elemento de combinación se muestran en orden ascendente.

Una permutación matemática es todos los posibles reordenaciones de n elementos. Por ejemplo, si n = 4, todas las posibles permutaciones enumeradas en orden lexicográfica son:

{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}

Cuando se trabaja con las permutaciones y combinaciones, dos funciones importantes son Choose(n,k) y Factorial(n). Es probable que esté familiarizado con la función Factorial(n), que a menudo se abrevia como n! La función Factorial(n) devuelve el número total de permutaciones de orden n. Por ejemplo:

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

La función Choose(n,k) devuelve el número total de combinaciones de k elementos seleccionados de n elementos.

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

Por ejemplo:

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

Las permutaciones y combinaciones forman parte de un área de estudio normalmente llamada combinatorio matemáticas o combinatorics sólo para short.

Una buena forma para que pueda ver mi objetivo en la columna de este mes es echar un vistazo a la captura de pantalla en La figura 1. He usado Windows PowerShell para host mi aplicación de demostración de F #, pero podríamos tener simplemente como utilizado fácilmente un shell de comandos. Aunque se ha modificado mi script de inicio de Windows PowerShell para desplazarse automáticamente a la ubicación de mi programa CombinatoricsDemo.exe.

Figura 1 Las combinaciones y permutaciones con F #

En segundo plano, las referencias de programa de demostración y las llamadas a una biblioteca de código F# denominado CombinatoricsLib. La demostración comienza con la lista de todas las combinaciones matemáticas de cinco elementos seleccionados tres a la vez. A continuación, se utiliza un método auxiliar para aplicar el último elemento de combinación {2,3,4} a una matriz de cadenas {ant, bat, vaca, perro, elk} para producir {vaca, perro, elk}: es decir, de las tres cadenas del conjunto original que se encuentran en los valores de índice 2, 3 y 4.

Mi programa de demostración continúa informática y mostrando el valor de Choose(200,10) varias maneras de seleccionar 10 elementos de un conjunto de 200 artículos orden no importa.

A continuación, el código de demostración calcula y muestra el valor de Factorial(52), que es el número total de formas de organizar las fichas de una baraja estándar de 52 cartas. Observe que el resultado es un número muy grande. Tal como explicaré, F # tiene la capacidad de trabajar con valores enteros arbitrariamente grande.

Mi programa de demostración concluye con una lista de todas las permutaciones matemáticas de orden n = 3.

En las secciones siguientes se describen en detalle código F # en el módulo CombinatoricsLib y el código en el programa de demostración de F # se muestra que se ejecutan en La figura 1. En el camino, comparo el uso de F # con otros lenguajes como Visual Basic y C# para trabajar con las permutaciones y combinaciones.

Esta columna se supone que se dispone de experiencia para principiantes a intermedio con un lenguaje .NET como C# y una familiaridad muy básica con F #. Pero incluso si está completamente nuevo a F #, debe poder seguir mis explicaciones sin demasiada dificultad.

La biblioteca de F # CombinatoricsLib

Para crear mi biblioteca combinatorics, usé la versión beta 2 de Visual Studio de 2010, que tiene el idioma de F # y las herramientas integradas. Espero el F # código que presento aquí para trabajar con la versión de lanzamiento de Visual Studio 2010 sin realizar ningún cambio significativo. Si estás utilizando una versión anterior de Visual Studio, puede encontrar herramientas F # en Microsoft F # Developer Center (MSDN.Microsoft.com/fsharp). También en el lenguaje de F #, Visual Studio 2010 se incluye con Microsoft .NET Framework 4, que utiliza mi biblioteca.

Creé mi biblioteca al iniciar Visual Studio 2010 y seleccionando archivo | nuevo | proyecto. En el cuadro de diálogo nuevo proyecto, he seleccionado la plantilla F# Library y había denominado Mi biblioteca CombinatoricsLib. Aparece la estructura general de mi CombinatoricsLib en Figura 2.

Figura 2 Estructura 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

El código de biblioteca comienza con código de Visual Studio ha generado que indica el nombre de mi biblioteca Module1. Había utilizado este nombre de predeterminado en su lugar nondescript en lugar de cambiar a algo más descriptivo para que la sintaxis para tener acceso a la biblioteca destaque más adelante en este artículo.

A continuación, he agregado dos F # abrir instrucciones para el nuevo espacio de nombres System.Numerics y nivel superior del espacio de nombres System para que puedo obtener acceso a las clases de estos espacios de nombres sin calificar totalmente los nombres de clase. El espacio de nombres System.Numerics forma parte de .NET Framework 4 y contiene una definición de BigInteger permite trabajar con valores enteros arbitrariamente grande.

Definir un tipo en F # es diferente de la definición de una clase de C# conceptualmente equivalente. La definición de tipo tiene una firma que contiene los argumentos de entrada para el constructor de tipo principal:

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

Esta firma significa, “ yo estoy definiendo un tipo denominado combinación tiene un principal constructor que acepta argumentos de int n (el número total de elementos) y k (el tamaño de subconjunto) y una matriz de enteros una que especifica los valores de combinación individuales, como {0,1,4}. ”

F # tipos pueden tener constructores secundarios opcionales, tales como los enumerados en Figura 2:

new(n : int, k : int) =

Tenga en cuenta que constructores secundarios utilizar la palabra clave nueva explicit en contraposición a constructores de tipo principal. Este constructor secundario acepta valores sólo para n y k. Con otros lenguajes de programación como C#, probablemente definiría el constructor más sencillo como el principal constructor, es decir, antes de constructores que aceptan argumentos. Pero como verá en F #, para los tipos con varios constructores, es mejor crear un tipo de modo que el principal constructor es una con la mayoría de los parámetros. La estructura de mi tipo de combinación continúa con tres funciones miembro:

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

La palabra clave this enlaza los métodos de miembros públicamente visibles al código de llamada externa. La función IsLast devuelve true si el objeto de combinación asociado es el último elemento en orden lexicográfica, como {2,3,4} para n = 5 y k = 3, tal y como se muestra en La figura 1.

La función sucesor devuelve el siguiente elemento de combinación en orden lexicográfica al elemento actual.

La función ApplyTo acepta una matriz de cadenas y devuelve una matriz de cadenas que corresponde al elemento de combinación actual.

Mi función miembro de tipo siguiente proporciona una forma de mostrar un elemento de combinación:

override this.ToString() : string =

Uso la palabra clave override para distinguir el método ToString base mi función personalizada de ToString. Dado que F # es un lenguaje. NET, todos los objetos heredan de un objeto de base comunes que tiene un método ToString. Observe que, aunque la función de ToString reemplazada tiene ámbito público, no se utilizan la palabra clave de miembro.

Las funciones dos últimos miembro en el tipo de combinación de definen las funciones Choose y factorial:

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

Ambas funciones son estáticas, lo que significa que las funciones son asociadas y llamar directamente desde el contexto del tipo de combinación en lugar de una instancia determinada de un objeto de combinación. Ambas funciones devuelven tipo BigInteger, definida en el espacio de nombres System.Numerics, que está directamente visible de manera predeterminada al código F #.

También en un tipo de combinación, definir un tipo de permutación tal y como se muestra en el listado en Figura 2.

La implementación de la biblioteca de F # Combinatorics

Ahora vaya let’s sobre los detalles de la implementación de la biblioteca CombinatoricsLib. Comienza el constructor principal de combinación:

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"

Curiosamente, para realizar la validación de argumento de entrada en un constructor principal debe utilizar la palabra clave pendientes, que indica una acción en lugar de en el valor predeterminado de un valor, que normalmente se supone por lenguajes funcionales como F #. La palabra clave failwith produce una excepción que se puede detectar mediante código de llamada.

A continuación, configuro los miembros privados de tipo de combinación:

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

La palabra clave deje que enlaza los valores a miembros privados. Tenga en cuenta que puedo utilizar minúsculas n y k como ambos parámetros de entrada y como campos privados. Esto parece un poco extraño y por lo tanto, en la mayoría de las situaciones uso notación mayúsculas para los parámetros o los miembros privados.

Copiar los valores de la matriz de argumentos de entrada una en el tipo de datos del campo utilizan un modismo F # estándar. El delimitadores [|. . |] indican una matriz mutable. El constructor de combinación secundario crea un objeto inicial de combinación y se define como:

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 #, constructores secundarios deben llamar al constructor principal. Por lo tanto, definir una matriz int denominada iniciadores con valores de 0 a través de 1 k y pásele junto con n y k al constructor principal. Este mecanismo F # es la razón por la que es aconsejable definir cualquier constructor principal como el constructor con la mayoría de los parámetros.

La función de miembro IsLast se define como:

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

In La figura 1, observe que sólo el último elemento de una lista de todas las combinaciones tiene el valor n-k ubicado en la primera posición de la matriz. F # no utiliza una palabra clave return explícita como hace la mayoría de los lenguajes; la devolución implícita es el último valor en una función, en este caso es true o false. El = símbolo (token) comprueba la igualdad en F # y no es un operador de asignación. La función Combination.Successor es:

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

Empezaré copiando los valores del objeto context de combinación actual en una matriz mutable denominada a temp. A continuación, defino una variable de índice denominada x y colóquela junto al final de la matriz temporal. Debo utilizar la palabra clave mutable para que puedo decremento esta variable de índice porque, de forma predeterminada, la mayoría de las variables de F # son inmutables. Utilizo el <-operador de asignación.

Una vez que se encuentra el índice de clave del objeto de combinación actual, incrementar ese valor y todos los valores a la derecha del índice de clave. A continuación, pasar la matriz temporal, que ahora tiene el valor del elemento de combinación sucesora, al constructor principal y devolver el objeto recién creado.

Observe que no devuelven null cuando estoy en el último elemento de combinación: en F # se considera poco pobre para ello. El código que presento en este artículo utiliza un estilo que no es muy F #-ish. F # expertos podrían utilizar un enfoque recursiva probablemente pero ya estoy suponiendo que está familiarizado con F #, quería que mi código F # como familiarizado como sea posible.

Un enfoque alternativo para escribir una función de sucesor es implementar la interfaz .NET IEnumerable.

La función ApplyTo proporciona una manera de asignar un elemento de combinación a un conjunto de valores de cadena:

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

Cuando la realización de argumento de entrada comprueba en una función miembro, no necesito utilizar la palabra clave que se requiere en los constructores de tipo. El método Array.zeroCreate estático crea una matriz de enteros inicializada a todos los valores 0 como cabría esperar. La función ApplyTo es fácil porque el intervalo de valores en una combinación de matemática con subconjunto tamaño k (0..k - 1) es exactamente el mismo los índices de cualquier matriz de .NET de k de tamaño.

La función de miembro reemplazada de ToString simplemente genera una cadena formada por valores del objeto de contexto:

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

Decidí delimitar Mis elementos de la combinación con el ^ carácter (símbolo de intercalación), que se inicia con la letra c y delimitar Mis elementos de permutación con el carácter % (porcentaje), que comienza con p, que me ayude a identificar si una cadena de dígitos representa una combinación o un objeto de permutación.

La función Choose estática se codifica como se muestra en Figura 3. 

Figura 3 La función Choose

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

En lugar de la informática elegir de la definición que se ha descrito anteriormente en este artículo, utilizo dos optimizaciones. En primer lugar, utilice el hecho de que elija (n, k) = elegir (n, n-k). Por ejemplo Choose(9,6) = Choose(9,3). En segundo lugar, en lugar de factoriales independiente tres de cálculo, cada uno de los cuales puede ser muy grande, calcule una serie de productos parciales. Para convertir valores int al tipo BigInteger de forma explícita, uso la función de bigint F # integrada.

La implementación del tipo de permutación es bastante similar a la implementación del tipo de combinación. Para obtener el código de origen de complete para la biblioteca CombinationLib desde el sitio Microsoft Code Gallery Web en code.msdn.microsoft.com.

Mediante el CombinatoricsLib

En esta sección explica cómo llamar a la función en la biblioteca CombinatoricsLib para producir la ejecución que se muestra en la captura de pantalla La figura 1. Empezaré iniciar Visual Studio 2010 y creando un nuevo proyecto de aplicación de F # llamado CombinatoricsDemo. El programa completo aparece en Figura 4.

Figura 4 Mediante el 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

Antes de escribir ningún código, hizo clic con el botón secundario del mouse en el nombre del proyecto en la ventana del explorador de soluciones de Visual Studio y había seleccionado la opción Agregar referencia en el menú contextual. He seleccionado la ficha Examinar y desplazado al ensamblado CombinatoricsLib.dll.

Primero el código del programa de demostración Agregar instrucciones abiertas a los ensamblados del sistema y Module1. Recuerde que el nombre del módulo de la CombinatorcsLib es Module1. Incluyo todas las instrucciones de programa en un bloque try / con bloqueo para capturar y controlar las excepciones. He creado una instancia de un objeto de combinación utilizando el constructor secundario para realizar una c de objeto inicial combinación matemática cinco elementos de tres a la vez: {0,1,2}. Utilizo el ingenioso F # %a especificador de formato, que indica a F # para inferir cómo imprimir mi objeto combinada. Podía haber utilizado también el formato de cadena %s.

A continuación, uso F # mientrasun bucle para recorrer en iteración y mostrar todos los elementos Combination(5,3) 10. En este momento, c de objeto de combinación es el último elemento y llame a la función ApplyTo para asignar esa combinación en una matriz de cadenas.

Observe que llamo a las funciones factorial y elija desde el contexto del tipo de combinación en lugar de en el objeto de combinación c. Después de llamar a código de tipo de permutación de manera similar, el programa de demostración concluye colocando la entrada del usuario con el método Console.ReadLine, donde canalizo el valor devuelto al objeto ignore integrados. Controlar las excepciones en el con bloque mostrando simplemente mensaje de error excepción.

También en llamar a una biblioteca F# desde un programa de F # como sólo he demostrado, se puede llamar a una biblioteca F# desde cualquier lenguaje compatible con. NET. Además, Visual Studio le permite utilizar útil F # interactiva ventana para realizar llamadas de ad hoc, como se muestra en Figura 5.

Figura 5 Uso interactivo de una biblioteca de F #

En la F # ventana interactiva en la parte inferior de la pantalla, agrega una referencia al ensamblado CombinatoricsLib escribiendo:

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

En este caso # r significa agregar una referencia y; termina una instrucción de F # interactiva. Ahora puedo interactivamente llamo las funciones en la biblioteca. ¡Fantástico!

En mi opinión, existen varias ventajas e inconvenientes al uso de F #. En el lado negativo, descubrí que la curva de aprendizaje para F # era mucho más pronunciada que yo esperaba. Escritura en un estilo funcional fue un cambio de paradigma grande para mí. Además, mucho más lo que otros lenguajes, F # tiene varias formas de codificación de una tarea determinada, que llevó me sienta uneasy acerca de si se escribió ningún código de F # que escribí de forma óptima.

Sin embargo, en mi caso al menos, me siento las ventajas de aprendizaje F # definitivamente compensan los costos. Cuando habla con codificadores de experimentados F #, más me dijo que en muchos casos, aunque en realidad hay varias formas de codificar una tarea, el enfoque adoptado es más una cuestión de preferencias personales de eficacia técnica. Además, codificación paradigmas (como inmutabilidad predeterminada) y dedicadas con sintaxis F # me diste qué sentía fue algunas buenas nociones de codificación en procedimientos lenguajes como C#.

Dr.James McCaffrey *trabaja en Volt Information Sciences Inc. dirigidos, donde encarga de formación técnica para los ingenieros de software que trabajan en Microsoft Redmond, Washington, campus. Ha trabajado en varios productos de Microsoft incluidos Internet Explorer y MSN Search. Dr. McCarthy es el autor de “ .NET Test Automation Recipes ” (Apress, 2006). Puede ponerse en jammc@microsoft.com.                     *

Gracias a los siguientes expertos técnicos por su ayuda en la revisión de este artículo:  Brian McNamara, Paul Newson y Matthew Podwysocki