E12 Anagramas
Faça o Web Exercise 4.2.12, Anagrams, de IntroCS:
http://introcs.cs.princeton.edu/java/42sort/
Seu programa deve chamar-se Anagrams.java. A entrada de seu programa será uma lista de palavras, dada na entrada padrão. Por exemplo, a entrada poderia ser a lista de palavras no arquivo exemplo.in:
$ java-introcs Anagrams < exemplo.in
+ aboard abroad
+ ascent secant stance
$
Note que cada linha da saída, que começa com '+', contém conjuntos de anagramas. A palavra "starch", que não tem anagrama em exemplo.in, não aparece na saída.
Seu programa deve ter complexidade \(O(N\log N)\), onde $N$ é o número de palavras na entrada. Você pode verificar seu programa com as entradas
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/sgb-words5.txt
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/words5.txt
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/words6.txt
https://www.ime.usp.br/~yoshi/DATA/500k_words
https://www.ime.usp.br/~yoshi/DATA/Pwords
As saídas correspondentes aos arquivos words5.txt e Pwords seguem abaixo.
Observações
1. No cálculo da complexidade, supomos que as palavras da entrada têm comprimento limitado.
2. Você pode supor que as entradas de seu programa serão tais que não haverá mais de, digamos, 100 palavras que são anagramas entre si, isto é, cada linha de sua saída não terá mais de 100 palavras.
3. Executando seu programa nas palavras em 500k_words, a saída deverá conter, por exemplo, as linhas
+ actuator's autocrat's
+ aspirant's partisan's
+ alumna's manual's
+ self-catering self-creating self-reacting
+ Anglo-latin all-atoning
4. Você pode achar conveniente lembrar que existe o método toCharArray() para transformar um String em um vetor de char e existe um construtor de String que recebe um vetor de char como argumento. Esse método e esse construtor são usados no programa Permutations.java em
https://www.ime.usp.br/~yoshi/2021ii/ccm0118/sandbox/2021.10.20/ENUMERACOES_RECURSIVAS/
- 30 novembro 2021, 20:47 PM
- 30 novembro 2021, 20:47 PM
- 30 novembro 2021, 20:47 PM