Imagino ter encontrado uma resposta para a questao 5.3.3-CLRS, se estah certa...eh outra estória, rs
Bom, a questao trata do fato se a função Permute-with-all(A) produz uma permutação aleatória uniforme, ou não.
Permute-with-all(A)
(1) n = comp.[A]
(2) for i=1 to n
(3) do trocarA[i] = A[RANDOM(1,n)]
Solução:
Façamos, antes de mais nada, um pequeno teste.
Tomemos um vetor de tamanho igual a 3. Assim, teremos 3 chamadas a função Random, a qual, retornará um dos 3 valores ( do vetor ) possíveis, logo teremos 27 possíveis saídas para a chamada de Permute-with-all(A).
Porém, nao podemos nos esquecer que dado um vetor de 3 posições teremos um total de 3! = 6 permutações possíveis. Logo, se Permute-with-all(A) produz uma distribuição (aleatória) uniforme, então cada permutação deverá ocorrer com uma probabilidade igual a 1/6.
Agora, fazendo-se com que T, seja o número de vezes que uma dada permutação ocorra, assim teremos:
( T / 27 ) = ( 1 / 6 )
Como podemos observar, não há valor inteiro para T que satisfaça esta equação, assim conclui-se que Permite-with-all (A) não produz uma permutação aleatória uniforme.
Bom, não sei...parece certo.
Se alguém ajudar ....agradeço.