O seguinte algoritmo gera uma permutação aleatória dos elementos . Ele é um pouco mais rápido do que aquele apresentado no Exemplo , mas é tal que nenhuma posiçāo é fixada até o término da execção. Neste algoritmopode ser interpretado como o elemento na posiçāo
Passo 1. Faça k=1.
Passo 2. Faça P(1)=1.
Passo 3. Se k = n, pare. Caso contrário, faça k = k + 1.
Passo 4. Gere um número aleatório U e faça
Volte para o passo 3.
a) Explique com palavras o que faz esse algoritmo.
b) Mostre que na iteraçăo k - isto é, quando o valor de P(k) é inicialmente ajustado ) é uma permutação aleatória de .
Passo 1
Fala galeraaa!
Vamos que vamos!
No item(a), temos:
O algoritmo vai da posição k = 1 para a posição k = n - 1 e em cada iteração ele escolhe um número do conjunto e substitui os valores na posição k e essa posição escolhida aleatoriamente.
No item(b), temos:
Vamos usar indução matemática. Para a base k = 1, a afirmação é trivialmente válida.
Suponha agora que a cla é verdadeira para k - 1. O que é para k? Como o valor na posição k em k a iteração é trocado pelo valor na posição aleatória, temos que:
Agora, use a hipótese de indução para obter que:
Então, temos:
que precisava ser provado.
Resposta
Use o princípio da indução matemática e a terceira etapa do algoritmo para obter a igualdade necessária.