Permutação aleatória

Origem: Wikipédia, a enciclopédia livre.

Uma permutação aleatória é um ordenação aleatória de um conjunto de objetos, isto é, uma variável aleatória com valor de permutação. O uso de permutações aleatórias é muitas vezes fundamental para campos que utilizam algoritmos aleatórios, tais como teoria de códigos, criptografia e simulação. Um bom exemplo de uma permutação aleatória é a embaralhar um baralho de cartas, isto é, idealmente, uma permutação aleatória de 52 cartas.

Gerando permutações aleatórias[editar | editar código-fonte]

Método de força bruta[editar | editar código-fonte]

Um método de geração de uma permutação aleatória de um conjunto de tamanho  uniformemente ao acaso (isto é, cada uma das permutações tem a mesma probabilidade de acontecer) é gerar uma sequência, tomando um número aleatório entre 1 e n sequencialmente, garantindo que não há repetição. Esta sequência  é interpretada como a permutação mostrada nesta notação.

Este método de força bruta exige novas tentativas sempre que o número aleatório escolhido já foi selecionado. Isso pode ser evitado se, na i-ésima etapa (quando já foi escolhido), um número j é escolhido aleatoriamente entre 1 e e igualamos  ao j-ésimo maior número não-escolhido.

Embaralhamento de Knuth[editar | editar código-fonte]

Um algoritmo simples para gerar uma permutação de itens uniformemente ao acaso sem repetições, conhecido como Embaralhamento de Knuth. O algoritmo começa com qualquer permutação (por exemplo, a permutação identidade), e então itera-se pelas posições 0 à (por convenção, o primeiro elemento tem o índice 0 e o último elemento tem o índice ), e para cada posição , troque o elemento que existe atualmente com um elemento escolhido aleatoriamente das posições a , inclusive. Verifica-se que qualquer permutação de elementos será produzida por este algoritmo com probabilidade exatamente , resultando assim, em uma distribuição uniforme sobre todas essas permutações.

unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = uniform(n-i); /* A random integer such that 0 ≤ j < n-i*/
        swap(permutation[i], permutation[i+j]);   /* Swap an existing element [i+j] to position [i] */
    }
}

Observe que a função uniforme() pode não ser implementada simplesmente como random() % (m), a menos que um viés nos resultados é aceitável.

Estatísticas sobre permutações aleatórias[editar | editar código-fonte]

Pontos fixos[editar | editar código-fonte]

A distribuição de probabilidade do número de pontos fixos de uma permutação aleatória uniformemente distribuída se aproxima de uma distribuição de Poisson com valor esperado 1 na medida que o valor de  cresce. Particularmente, é uma aplicação elegante do princípio de inclusão-exclusão que mostra que a probabilidade de que não existem pontos fixos se aproxima de . O primeiro n momentos desta distribuição são exatamente demonstrados pela distribuição de Poisson.

Teste de aleatoriedade[editar | editar código-fonte]

Como com todos os processos aleatórios, a qualidade da distribuição resultante de uma implementação de um algoritmo randomizado, como o algoritmo de Knuth (isto é, o quão próximo o algoritmo é da distribuição uniforme desejada) depende da qualidade da fonte de base de aleatoriedade, como um gerador de números pseudo-aleatórios. Existem muitos possíveis testes de aleatoriedade de permutações aleatórias, tais como os testes de Diehard. Um exemplo típico de tal teste é tomar alguma permutação estatística, para a qual a distribuição é conhecida, e testar se a distribuição de um conjunto de permutações gerados aleatoriamente se aproxima da verdadeira distribuição.

Ver também[editar | editar código-fonte]

  • Fórmula de amostragem de Ewens — uma ligação com a genética de populações
  • Embaralhamento de Faro
  • Embaralhamento de Fisher-Yates
  • Constante de Golomb–Dickman
  • Estatísticas de permutação aleatória
  • Algoritmos de Embaralhamento — método da ordenação aleatória, método de troca iterativo

Ligações externas[editar | editar código-fonte]