O seguinte algoritmo gera uma permutação aleatória dos elementos 1,2 ,   … ,   n . Ele é um pouco mais rápido do que aquele apresentado no Exemplo 1 a , mas é tal que nenhuma posiçāo é fixada até o término da execção. Neste algoritmo ,   P ( i )   pode ser interpretado como o elemento na posiçāo i .

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

P k = P k U + 1

P ( [ k U ] + 1 ) = k

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 -   P 1 ,   P 2 ,   … ,   P ( k ) é uma permutação aleatória de 1,2 ,   … ,   k .

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 { 1 ,   … ,   n } 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:

P k { i 1 ,   i 2 ,   … ,   i j - 1 ,   k ,   i j ,   … ,   i k - 2 ,   i     = P k - 1 i 1 ,   i 2 ,   … ,   i j - 1 ,   i ,   i j ,   … ,   i k - 2 1 k  

Agora, use a hipótese de indução para obter que:

P k - 1 { i 1 ,   i 2 ,   … ,   i j - 1 ,   i ,   i j ,   … ,   i k - 2 }   = 1 k - 1 !

Então, temos:

P k { i 1 ,   i 2 ,   … ,   i j - 1 ,   k ,   i j ,   … ,   i k - 2 ,   i }   = 1 k !

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.