Permutação aleatória
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