MAC0122 Princípios de Desenvolvimento de Algoritmos (2023ii, EC/EP)

Já estudamos em detalhe como resolver o Creative Exercise 2.3.17, Permutations, de IntroCS:

https://introcs.cs.princeton.edu/java/23recursion/

Escreva uma variante de Permutations.java, chamado PermutationsDeluxe.java, que recebe um string não vazio na entrada padrão e que imprime todas as permutações do string dado. O string dado pode ter letras repetidas, e é uma exigência neste exercícios que as permutações impressas sejam todas distintas. O string dado será sobre o alfabeto das letras a..z e A..Z.

Se você usar os algoritmos implementados em Permutations.java vistos em sala, a saída conterá strings repetidos se o string de entrada tiver letras repetidas, e assim aqueles algoritmos não resolvem este exercício. Para resolver este exercício, você pode fazer uma pequena adaptação daqueles algoritmos.

Exemplos de execução. Seu programa deve comportar-se como nos exemplos abaixo. A ordem dos strings na saída pode ser diferente em seu programa.

Observações. (1) Nos exemplos abaixo, usamos o comando echo, que simplesmente envia para a saída padrão os argumentos que ele recebe na linha de comando. (2) O programa Generate.java segue abaixo (ele serve para gerar instâncias para PermutationsDeluxe.java). (3) Quando executado com um argumento qualquer, PermutationsDeluxe.java deve ter como saída apenas o número de permutações geradas pelo seu algoritmo (seu programa deve gerar as permutações explicitamente, mas não deve imprimi-las; seu programa deve contar as permutações geradas e deve imprimir o número de permutações geradas).

$ echo exemplo de uso de echo
exemplo de uso de echo
$ echo abc | java-introcs PermutationsDeluxe
abc
acb
bac
bca
cba
cab
6 permutations
$ echo aaaa | java-introcs PermutationsDeluxe
aaaa
1 permutation
$ echo aab | java-introcs PermutationsDeluxe
aab
aba
baa
3 permutations
$ echo aabb | java-introcs PermutationsDeluxe
aabb
abab
abba
baab
baba
bbaa
6 permutations
$ echo ABBCCC | java-introcs PermutationsDeluxe
ABBCCC
ABCBCC
ABCCBC
[...]
CCCBBA
60 permutations
$ echo ABBCCC | java-introcs PermutationsDeluxe .
60 permutations
$ java-introcs Generate 1 2 3
abbccc
$ java-introcs Generate 1 2 3 | java-introcs PermutationsDeluxe .
60 permutations
$ java-introcs Generate 2 2 2 | java-introcs PermutationsDeluxe .
90 permutations
$ java-introcs Generate 2 2 2 2 | java-introcs PermutationsDeluxe .
2520 permutations
$ java-introcs Generate 2 2 2 2 2 | java-introcs PermutationsDeluxe .
113400 permutations
$ java-introcs Generate 2 2 2 2 2 2 | java-introcs PermutationsDeluxe .
7484400 permutations
$ time java-introcs Generate 8 8 | java-introcs PermutationsDeluxe .
12870 permutations

real 0m0.186s
user 0m0.181s
sys 0m0.081s
$ time java-introcs Generate 8 8 4 | java-introcs PermutationsDeluxe .
62355150 permutations

real 0m1.681s
user 0m1.713s
sys 0m0.157s
$ time java-introcs Generate 8 8 5 | java-introcs PermutationsDeluxe .
261891630 permutations

real 0m6.382s
user 0m6.457s
sys 0m0.224s
$ time java-introcs Generate 8 8 6 | java-introcs PermutationsDeluxe .
960269310 permutations

real 0m22.938s
user 0m23.139s
sys 0m0.483s
$ time java-introcs Generate 8 8 7 | java-introcs PermutationsDeluxe .
3155170590 permutations

real 1m13.800s
user 1m14.436s
sys 0m1.271s
$

Desempenho. Seu programa deve demorar, grosso modo, tempo proporcional ao número de permutações geradas.

Sugestão. Você pode achar interessante usar um vetor booleano "indexado por caracteres". Em Java, o tipo char é basicamente equivalente a um inteiro (mais precisamente, um inteiro curto sem sinal (16 bits)). A tradução entre caracteres e inteiros é feita usando-se uma tabela de conversão padrão. Os programas anexos dão dicas de como manipular vetores inteiros indexados por chars. Em seu programa, você poderá achar conveniente usar um vetor de booleanos.

Entrega.  Entregue apenas seu programa PermutationsDeluxe.java (note que seu programa deve obrigatoriamente ter este nome).