Este artigo foi traduzido por máquina.

Execução de teste

Combinações e permutas com o F#

James McCaffrey

Baixe o código de exemplo

A compreensão de combinações e permutas é uma habilidade fundamental no teste de software. Coluna execução de teste deste mês mostro como trabalhar com combinações e permutações usando código escrito na linguagem F # nova.

Uma combinação de matemática é um subconjunto de k itens selecionados em um conjunto de itens n, onde a ordem não importa. Para um amplo ex se n = 5 e k = 2, todas as maneiras possíveis para selecionar dois itens de cinco itens são:

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

Observe que eu não liste a combinação de 1,0 {} porque ele é considerado igual {0,1}. Além disso, eu ter listados os 10 combinações de cinco itens selecionados dois ao mesmo tempo usando o que é chamado lexicographical ordem, onde os valores em cada elemento de combinação são listados em ordem crescente.

Uma matemática permutação é rearrangements possíveis todos os n itens. Por exemplo, se n = 4, todas as possíveis permutações listadas em ordem lexicographical são:

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

Ao trabalhar com combinações e permutações, duas funções importantes são Choose(n,k) e Factorial(n). Você provavelmente está familiarizado com a função Factorial(n), que é freqüentemente abreviada como n! A função Factorial(n) retorna o número total de permutações de ordem n. Por exemplo:

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

A função Choose(n,k) retorna o número total de combinações de itens k n itens selecionados.

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

Por exemplo:

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

Combinações e permutações fazem parte de uma área de estudo, normalmente chamado de matemática combinatorial ou combinatorics apenas de forma abreviada.

Uma boa maneira de ver em que eu estou cabeças na coluna deste mês é dar uma olhada a captura de tela em Figura 1. Usei o Windows PowerShell para hospedar o meu aplicativo de demonstração do F #, mas eu poderia ter tão usados facilmente um shell de comando. Modifiquei o meu script de inicialização do Windows PowerShell para navegar automaticamente para o local do meu programa CombinatoricsDemo.exe.

Figura 1 Combinações e permutações com F #

Nos bastidores, as referências do programa de demonstração e chamadas em uma biblioteca de código F # nomeados CombinatoricsLib. A demonstração começa listando todas as combinações de matemáticas de cinco itens selecionados três por vez. Em seguida, ele usa um método auxiliar para aplicar o último elemento combinação 2,3,4 {}, uma matriz de seqüências de caracteres {ant, bat, vaca, cachorro, elk} para produzir {vaca, cachorro, elk} — ou seja, as três seqüências do conjunto original que estão localizadas em valores de índice 2, 3 e 4.

Meu programa de demonstração continua de computação e exibindo o valor de Choose(200,10), o número de maneiras de selecionar 10 itens de um conjunto de 200 itens em que ordem não importa.

Em seguida, o código de demonstração calcula e exibe o valor de Factorial(52), que é o número total de maneiras de organizar as placas em um baralho padrão de 52 cartas. Observe que o resultado é um número muito, muito grande. Como explicarei, F # tem a capacidade de trabalhar com valores inteiros arbitrariamente grandes.

Meu programa de demonstração conclui listando todas as permutações de matemáticas de ordem n = 3.

As seções a seguir, descrevo detalhadamente o código F # no módulo CombinatoricsLib e o código do programa de demonstração da linguagem F # mostrado em execução na Figura 1. Ao longo do caminho compare o uso do F # com outras linguagens, como Visual Basic e translation from VPE for Csharp para trabalhar com combinações e permutações.

Esta coluna pressupõe que você tenha experiência de iniciante a intermediário com uma linguagem .NET such as translation from VPE for Csharp e familiaridade básica com F #. Mas, mesmo se você estiver completamente novo para a linguagem F #, você deve ser capaz de acompanhar minhas explicações sem muita dificuldade.

A biblioteca de F # CombinatoricsLib

Para criar a minha biblioteca combinatorics, usei a versão beta 2 do Visual Studio 2010, que tem as ferramentas internas e a linguagem F #. Espero que o código F # apresentadas aqui para trabalhar com a versão de lançamento do Visual Studio 2010 sem alterações significativas. Se você estiver usando uma versão anterior do Visual Studio, você pode encontrar as ferramentas do Microsoft F # Developer Center (msdn.microsoft.com/fsharp). Juntamente com a linguagem F #, Visual Studio 2010 é fornecido com o Microsoft .NET Framework 4, que usa minha biblioteca.

Eu criados minha biblioteca pelo iniciando o Visual Studio 2010 e selecione File | New | Project. Na caixa de diálogo Novo do projeto, eu selecionado o modelo Biblioteca de F # e chamada minha biblioteca CombinatoricsLib. A estrutura geral do meu CombinatoricsLib está listada no Figura 2.

Figura 2 Estrutura da linguagem 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

O código da biblioteca começa com o código gerado pelo Visual Studio que nomeia a minha biblioteca Module1. Eu usado esse nome em vez disso nondescript padrão em vez de alteração para algo mais descritivo para que a sintaxe para acessar a biblioteca destacará neste artigo.

Em seguida, adicionei dois F # abrir instruções para o namespace System nível superior e o novo namespace System.Numerics para que poder acessar as classes nesses espaços para nome sem qualificar totalmente os nomes de classe. O namespace System.Numerics faz parte do .NET Framework 4 e contém uma definição BigInteger que permite trabalhar com valores inteiros arbitrariamente grandes.

Definindo um tipo em F # é diferente de definir uma classe translation from VPE for Csharp conceitualmente equivalente. A definição de tipo tem uma assinatura que contém os argumentos de entrada para o construtor de tipo primário:

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

Essa assinatura significa “ eu estou definindo um tipo chamado combinação que tem um construtor primário aceita int argumentos n (o número total de itens) e k (o tamanho do subconjunto) e uma matriz de inteiros um que especifica os valores individuais de combinação, como {0,1,4}. ”

Tipos de F # podem ter construtores secundários opcionais, como o listado em Figura 2:

new(n : int, k : int) =

Observe que os construtores secundários usar a palavra-chave new explícita ao contrário de tipo primário construtores. Esse construtor secundário aceita valores somente para n e k. Com outras linguagens de programação such as translation from VPE for Csharp, você provavelmente definiria o construtor mais simples do construtor primário, isto é, antes de construtores que aceitam argumentos. Mas como você verá no F #, para tipos com vários construtores, é geralmente melhor criar um tipo de forma que o construtor primário é aquele com a maioria dos parâmetros. A estrutura do meu tipo de combinação continua com três funções de membro:

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

A palavra-chave this vincula métodos de membro publicamente visíveis ao código de chamada externo. A função IsLast retorna true se o objeto combinação associado for o último elemento na ordem lexicographical, como {2,3,4} para n = 5 e k = 3, conforme mostrado no Figura 1.

A função sucessor retorna o próximo elemento de combinação na ordem lexicographical para o elemento atual.

A função ApplyTo aceita uma matriz de seqüências de caracteres e retorna uma matriz de seqüências de caracteres que corresponde ao elemento combinação atual.

Minha próxima função de membro de tipo fornece uma maneira de exibir um elemento de combinação:

override this.ToString() : string =

Uso a palavra-chave override para diferenciar minha função ToString personalizada do método ToString base. Como a linguagem F # é uma linguagem .NET, todos os objetos herdam de um objeto de base comum que tem um método ToString. Observe que, embora a função ToString substituída tenha escopo público, eu não uso a palavra-chave do membro.

As funções de dois últimos membro no tipo de combinação definem as funções de escolha e fatorial:

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

Ambas as funções são estáticas, o que significa que as funções estão associadas com e chamadas diretamente a partir do contexto do tipo de combinação, em vez de uma instância específica de um objeto de combinação. Ambas as funções retornam tipo BigInteger, definido no namespace System.Numerics, que são diretamente visível por padrão para código F #.

Juntamente com um tipo de combinação, posso definir um tipo de permutação como mostra a listagem de Figura 2.

A implementação da biblioteca de F # Combinatorics

Agora let’s examine os detalhes da implementação da biblioteca CombinatoricsLib. O construtor primário combinação começa:

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, você deve usar a palavra-chave, que indica uma ação, em vez de padrão de um valor, que normalmente é assumido por linguagens funcionais, como F # para executar a validação de argumento de entrada em um construtor primário. A palavra-chave failwith lança uma exceção, que pode ser detectada pelo código de chamada.

Em seguida, configuro os membros privados de tipo de combinação:

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

A palavra-chave permitem que vincula os valores a membros privados. Observe que eu pode usar n minúsculo e k como os dois parâmetros de entrada e como campos particulares. Isso parece um pouco estranho e então na maioria das situações uso notação maiúsculas para os parâmetros ou membros privados.

Copiando os valores da matriz de argumento de entrada um para o tipo de dados do campo usam um idioma padrão do F #. O [|. . |] delimitadores indicam uma matriz mutável. O construtor de combinação secundário cria um objeto combinação inicial e é definido 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)

No F #, construtores secundários devem chamar o construtor primário. Portanto, eu definir uma matriz int chamada acionadores de partida com valores de 0 a 1 k e passá-lo juntamente com n e k para o construtor primário. Esse mecanismo F # é por isso, é aconselhável definir qualquer construtor primário como o construtor com a maioria dos parâmetros.

A função de membro IsLast é definida como:

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

In Figura 1, observe que somente o último elemento em uma lista de todas as combinações tem valor localizado na primeira posição da matriz de n-k. F # não está usando uma palavra-chave return explícita assim como a maioria dos idiomas; retorno implícito é o último valor em uma função, nesse caso true ou false. O = token verificações de igualdade em F # e não é um operador de atribuição. A função Combination.Successor é:

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

Começo, copiando os valores de contexto do objeto combinação atual em um array mutável chamado temp. Em seguida, defino uma variável de índice denominada x e posicione-a no final da matriz temp. Eu deve usar a palavra-chave mutável para que eu pode diminuir essa variável de índice porque, por padrão, a maioria das variáveis em F # são imutáveis. Eu uso o <-operador de atribuição.

Depois que eu localizar o índice de chave do objeto combinação atual, eu incrementar esse valor e todos os valores à direita do índice de chave. Em seguida, transfiro a matriz temp, que agora tem o valor do elemento de combinação sucessoras, para o construtor primário e retorna o objeto recém-criado.

Observe que eu não retornam null quando estou no último elemento combinação — em F # é considerada estilo ruim para fazer isso. O código apresentadas neste artigo usa um estilo que não seja muito F #-ish. Especialistas em F # provavelmente usaria um método recursivo, mas porque eu estou supondo que você for novo na linguagem F #, eu gostaria de tornar meu código F # tão familiar possível.

Uma abordagem alternativa para escrever uma função sucessor é implementar a interface .NET IEnumerable.

A função ApplyTo fornece uma maneira de mapear um elemento de combinação para um conjunto de valores de seqüência:

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

Quando executar o argumento de entrada verifica em uma função de membro, não preciso usar a palavra-chave conforme o necessário em construtores de tipo. O método estático Array.zeroCreate cria uma matriz de inteiros inicializada para todos os valores 0 como esperado. A função ApplyTo é fácil porque o intervalo de valores em uma combinação de matemática com subconjunto tamanho k (0..k - 1) é exatamente o mesmo que os índices de qualquer matriz .NET de tamanho k.

A função de membro substituída ToString simplesmente cria uma cadeia de caracteres formada por valores do 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

Decidi delimitar meus elementos de combinação com o ^ caractere (circunflexo), que começa com a letra c e para delimitar meus elementos de permuta com o caractere % (percentual), que começará com p para me ajudar a identificar se uma seqüência de dígitos representa uma combinação ou de um objeto de permuta.

A função estática de escolha é codificada como mostrado no Figura 3. 

Figura 3 Função 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

Em vez de computar a escolha da definição do descrito neste artigo, uso duas otimizações. Em primeiro lugar, utilizo o fato dessa escolha (n, k) = escolher (n, n-k). Por exemplo Choose(9,6) = Choose(9,3). Segundo, em vez de três fatoriais separado computação, cada um deles pode ser muito grande, calcular uma série de produtos parciais. Para converter valores int digitar BigInteger explicitamente, posso usar a função de bigint F # interna.

A implementação do tipo de permuta é bem semelhante à implementação do tipo de combinação. Você pode obter o código-fonte complete para a biblioteca CombinationLib do site Microsoft Code Gallery no code.msdn.microsoft.com.

Usando o CombinatoricsLib

Nesta seção, explique como chamar a função na biblioteca CombinatoricsLib para produzir a execução mostrada na captura de tela Figura 1. Começo iniciando o Visual Studio 2010 e criar um novo projeto F# Application chamado CombinatoricsDemo. O programa inteiro está listado em Figura 4.

Figura 4 Usando o 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 escrever qualquer código, eu clicou com o botão direito do mouse no nome do projeto na janela Solution Explorer do Visual Studio e selecionou a opção Add Reference no menu de contexto. Eu selecionada na guia Procurar e navegar para o assembly CombinatoricsLib.dll.

Começo o código de programa de demonstração ao adicionar instruções abertas aos assemblies Module1 e sistema. Lembre-se de que o nome do módulo do CombinatorcsLib é Module1. Concluir todas as instruções do programa em um bloco try / com bloco para capturar e manipular exceções. Eu instancio um objeto de combinação usando o construtor secundário para fazer um c de objeto inicial combinação matemática de cinco itens executada três por vez: {0,1,2}. Uso o elegantes F # %A especificador de formato, que instrui o F # para inferir como imprimir meu objeto de combinação. Eu também poderia ter usado o formato da seqüência de caracteres %s.

Em seguida, uso a F # e, ao mesmo tempoum loop para iterar e exibir todos os elementos Combination(5,3) 10. Neste ponto, o c de objeto de combinação é o último elemento e eu chamar a função ApplyTo para mapear essa combinação em uma matriz de seqüências de caracteres.

Observe que eu chamar as funções escolher e fatorial do contexto do tipo de combinação, em vez do objeto combinação c. Depois de chamar o código do tipo de permutação de forma semelhante, o programa de demonstração conclui pausando entrada do usuário com o método console.ReadLine, onde eu canalizar o valor de retorno para o objeto interno ignorar. Posso tratar qualquer exceção nas com bloco, simplesmente exibindo a mensagem de erro de exceção.

Como chamar uma biblioteca de F # de um programa do F # como demonstrei apenas, você pode chamar uma biblioteca de F # em qualquer linguagem compatível com. NET. Além disso, o Visual Studio permite que você usar a janela de interativa útil F # para fazer chamadas de ad hoc, conforme mostrado no Figura 5.

Figura 5 Uso interativo de uma biblioteca de F #

Na linguagem F # interativa janela na parte inferior da tela, posso adicionar uma referência ao assembly CombinatoricsLib digitando:

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

Nesse caso, # r significa adicionar uma referência e; termina uma instrução em F # interativa. Agora eu interativamente podem chamar as funções na biblioteca. Elegantes!

Na minha opinião, há vários prós e contras ao uso do F #. No lado negativo, descobri que a curva de aprendizado para F # foi muito acentuada do que o esperado. Gravação em um estilo funcional foi uma mudança de paradigma grande para mim. Além disso, muito assim que outros idiomas, F # possui várias formas de codificação de uma tarefa específica, que levou me sentir uneasy sobre se qualquer código F # que escrevi foi escrito de maneira ideal.

No entanto, no meu caso pelo menos, sinto as vantagens do aprendizado F # definitivamente superam os custos. Ao conversar com experientes codificadores F #, a maioria me disse que em muitos casos, mesmo que haja na verdade várias maneiras de codificar uma tarefa, a abordagem utilizada é mais uma questão de preferência pessoal que técnicos eficiência. Além disso, combatendo com a sintaxe da F # e codificação paradigmas (como o padrão de imutabilidade) me deu o que senti foi algum esclarecimento boa codificação em linguagens de procedimento such as translation from VPE for Csharp.

Dr. James McCaffrey* trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software que trabalham com a Microsoft Redmond, Wash., campus. Ele trabalhou em vários produtos da Microsoft, incluindo o Internet Explorer e o MSN Busca. Dr. McCarthy é autor de “ .NET Test Automation Recipes ” (Apress, 2006). Ele pode ser contatado em jammc@microsoft.com.                     *

Graças aos seguintes especialistas técnicos para revisar este artigo:  Brian McNamara, Paul Newson e Matthew Podwysocki