T07 Geração de permutações
Considere o programa PermArray.java fornecido abaixo. Quando executado com argumento de linha de comando \(N\), ele imprime todas as permutações dos números em $U_N=\{0,\dots,N-1\}$. A chamada perm(a) em main() é responsável pela impressão da saída neste programa. Neste exercício, você deve provar que, de fato, perm(a) imprime as $N!$ permutações de $U_N$ quando o vetor a é inicializado como em PermArray.java. (No que segue, supomos que o vetor a é inicializado como em PermArray.java.)
Para fazer este exercício, formule uma afirmação $A_n$ ($0\leq n<N$) que descreve o efeito da execução da chamada perm(a, n). Sua afirmação $A_n$ deve ser tal que, quando $n=0$, a afirmação $A_n$ implica que perm(a, n) imprime todas as $N!$ permutações dos elementos no vetor a. Prove que $A_n$ vale por indução em $N - n$.
Conclua que, de fato, a chamada perm(a) em main() de PermArray.java imprime as $N!$ permutações de $U_N$.
Observação. Seja cuidadoso na formulação de $A_n$. Com a formulação correta de $A_n$, o passo de indução não será difícil.
- 26 de octubre de 2023, 18:55