E12 Anagramas
Neste exercício, você resolverá o Web Exercise 1.4.12 de Algs4:
https://algs4.cs.princeton.edu/14analysis/
Seu programa deve chamar-se Anagrams.java. Seu programa deve receber uma lista de palavras na entrada padrão e deve encontrar os anagramas na lista dada. Por exemplo, considere o arquivo exemplo.in dado abaixo. Seu programa deve comportar-se da seguinte forma:
$ java-algs4 Anagrams < exemplo.in
+ aboard abroad
+ ascent secant stance
$
Note que cada linha da saída começa com '+' e contém uma lista de anagramas, com cada anagrama precedido por um espaço. A palavra "starch", que não tem anagrama em exemplo.in, não aparece na saída. Seu programa deve também poder receber um inteiro como argumento de linha de comando. Ao receber o inteiro \(k\), seu programa deve imprimir apenas as linhas que contêm pelo menos $k$ anagramas. Assim, a execução sem argumento de linha de comando é equivalente à execução com argumento $2$. Seguem mais duas execuções de Anagrams.java:
$ java-algs4 Anagrams 3 < exemplo.in
+ ascent secant stance
$ java-algs4 Anagrams 4 < exemplo.in
$
Ordem da saída. Vamos adotar o seguinte formato rígido para a saída:
(1) As palavras em cada linha devem estar ordenadas em ordem alfabética.
(2) As linhas devem estar ordenadas em ordem alfabética de acordo com a primeira palavra de cada linha: se a linha $l_1$ começa com a palavra $p_1$ e a linha $l_2$ começa com a palavra $p_2$ e $p_1$ vem antes de $p_2$ na ordem alfabética, então $l_1$ deve ocorrer antes de $l_2$ em sua saída.
O programa IsSorted.java abaixo pode ser usado para verificar se a saída de seu programa segue o formato descrito acima.
Entrada. Você pode supor que a entrada é constituída de strings separados por espaços e assim você pode ler a entrada assim:
String[] words = StdIn.readAllStrings();
Ademais, você pode supor que não há strings repetidos na entrada. Os strings na entrada não estão necessariamente ordenados.
Ordem alfabética. Por simplicidade, neste exercício, interpretamos "ordem alfabética" como a ordem definida pelo método compareTo() da classe String (ordem induzida pela tabela Unicode).
Complexidade. Seu programa deve ter complexidade \(O(N\log N)\), onde $N$ é o número de palavras na entrada. (Nesta análise de complexidade, supomos que as palavras na entrada têm tamanho $O(1)$.) Você pode verificar seu programa com as entradas
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/words5.txt
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/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 acima seguem abaixo.
Você pode usar o programa Generator.java dado abaixo para gerar instância maiores e assim verificar experimentalmente a complexidade de seu algoritmo (Generator.java usa um objeto de um tipo que ainda não conhecemos, a saber, um objeto do tipo SET<String>, que serve para armazenar um conjunto de Strings).
Observação. Executando seu programa nas palavras em 500k_words, a saída deverá conter, por exemplo, as linhas
+ Anglo-chinese shoe-cleaning
+ actuator's autocrat's
+ alumna's manual's
+ aspirant's partisan's
+ self-catering self-creating self-reacting
Exemplos de execução. Exemplos de execução são dados nos arquivos experiments*.txt. Note que espera-se que seus tempos de execução sejam, grosso modo, comparáveis (leia sobre md5 e md5sum abaixo).
Message-digest MD5. O MD5$(s)$ de um string $s$ é uma cadeia 128 bits que distingue $s$ de strings $t$ diferentes $s$ de forma bastante efetiva: se $t$ é diferente de $s$, então MD5$(t)$ é, muito provavelmente, diferente de MD5$(s)$. Assim, quando MD5$(s)$ coincide com MD5$(t)$, é bastante provável que $s=t$. No GNU/Linux, você pode usar o programa md5sum para calcular o MD5 de um string $s$. No macOS, você pode usar o programa md5. Em alguns dos exemplos dados nos arquivos experiments*.txt, o MD5 da saída é determinado, para você poder comparar sua saída com a saída nesses exemplos.
$ java-algs4 Anagrams < exemplo.in > exemplo.out
$ md5 exemplo.out
MD5 (exemplo.out) = c4d5fffb60a90948d3e3b802ad11d0d5
$ java-algs4 Anagrams < exemplo.in | md5
c4d5fffb60a90948d3e3b802ad11d0d5
$
O MD5 é dado como um número em base hexadecimal com $32=2^5$ "dígitos". Cada "dígito" hexadecimal corresponde a $4=2^2$ bits, dando assim um total de $2^7=128$ bits.
Classe auxiliar obrigatória. Qual é sua ideia para identificar anagramas? Tente pensar em um método eficiente. Pense nesse problema antes de continuar a ler esse enunciado.
Ao pensar no problema acima, você provavelmente chegou à ideia que é sugerida por esse requisito deste exercício: neste exercício, use, obrigatoriamente, a classe auxiliar SignedWord.java fornecida abaixo.
Sugestões. Sugere-se fortemente que você faça o seguinte: para montar cada linha de sua saída, coloque as palavras que devem ser incluídas naquela linha em uma fila de Strings (isto é, em um objeto do tipo Queue<String>). Para montar a lista de linhas de sua saída, use uma fila de filas de Strings (mais precisamente, um Queue<Queue<String>>). Note que, ao fazer assim, você não precisa se preocupar nem com o número de palavras em cada linha, nem com o número total de linhas em sua saída (não seria assim se você usasse arrays).
Para ordenar as linhas para produzir a saída (lembre que as linhas devem estar ordenadas), transforme sua fila de filas em um array de filas. Use então ordenação indireta (isto é, use, por exemplo, o método Merge.indexSort()).
Entrega. Entregue apenas seu programa Anagrams.java.
- 23 novembro 2021, 10:05 AM
- 23 novembro 2021, 10:05 AM