# 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
### Método de força bruta

Um método de geração de uma permutação aleatória de um conjunto de tamanho $n$ uniformemente ao acaso (isto é, cada uma das $n!$ 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 $(x_{1},\ldots ,x_{n})$ é interpretada como a permutação mostrada nesta notação.
    ${\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},$
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 $x_{1},\ldots ,x_{i-1}$ já foi escolhido), um número j é escolhido aleatoriamente entre 1 e $n-i+1$ e igualamos $x_{i}$ ao j-ésimo maior número não-escolhido.

### Embaralhamento de Knuth

Um algoritmo simples para gerar uma permutação de $n$ 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 à $n-2$ (por convenção, o primeiro elemento tem o índice 0 e o último elemento tem o índice $n-1$), e para cada posição $i$, troque o elemento que existe atualmente com um elemento escolhido aleatoriamente das posições $i$ a $n-1$, inclusive. Verifica-se que qualquer permutação de $n$ elementos será produzida por este algoritmo com probabilidade exatamente $1/n!$, resultando assim, em uma distribuição uniforme sobre todas essas permutações.
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
### Pontos fixos

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 $n$ 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 $1/e$. O primeiro n momentos desta distribuição são exatamente demonstrados pela distribuição de Poisson.

## Teste de aleatoriedade

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.