И здесь - мое новое решение.
Книга Джона Бентли «Программирование жемчуга» содержит проблему поиска анаграмм слов.
Утверждение:
Учитывая словарь английских слов, найдите все наборы анаграмм. За
Например, «горшки», «стоп» и «вершины» являются анаграммами друг друга
потому что каждый может быть сформирован путем перестановки букв других.
Я немного подумал, и мне пришло в голову, что решение будет заключаться в том, чтобы получить подпись искомого слова и сравнить его со всеми словами в словаре. Все анаграммы слова должны иметь одинаковую подпись. Но как этого добиться? Моя идея заключалась в использовании фундаментальной теоремы арифметики:
Основная теорема об арифметике гласит, что
каждое положительное целое число (кроме числа 1) может быть представлено в
ровно в одну сторону от перегруппировки как произведение одного или нескольких
штрихи
Таким образом, идея состоит в том, чтобы использовать массив первых 26 простых чисел. Затем для каждой буквы в слове мы получаем соответствующее простое число A = 2, B = 3, C = 5, D = 7… и затем вычисляем произведение нашего входного слова. Затем мы делаем это для каждого слова в словаре и, если слово соответствует нашему входному слову, мы добавляем его в итоговый список.
Производительность более или менее приемлема. Для словаря из 479828 слов требуется 160 мс, чтобы получить все анаграммы. Это примерно 0,0003 мс / слово или 0,3 мкс / слово. Кажется, что сложность алгоритма составляет O (mn) или ~ O (m), где m - размер словаря, а n - длина входного слова.
Вот код:
package com.vvirlan;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Words {
private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113 };
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String word = "hello";
System.out.println("Please type a word:");
if (s.hasNext()) {
word = s.next();
}
Words w = new Words();
w.start(word);
}
private void start(String word) {
measureTime();
char[] letters = word.toUpperCase().toCharArray();
long searchProduct = calculateProduct(letters);
System.out.println(searchProduct);
try {
findByProduct(searchProduct);
} catch (Exception e) {
e.printStackTrace();
}
measureTime();
System.out.println(matchingWords);
System.out.println("Total time: " + time);
}
private List<String> matchingWords = new ArrayList<>();
private void findByProduct(long searchProduct) throws IOException {
File f = new File("/usr/share/dict/words");
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ((line = br.readLine()) != null) {
char[] letters = line.toUpperCase().toCharArray();
long p = calculateProduct(letters);
if (p == -1) {
continue;
}
if (p == searchProduct) {
matchingWords.add(line);
}
}
br.close();
}
private long calculateProduct(char[] letters) {
long result = 1L;
for (char c : letters) {
if (c < 65) {
return -1;
}
int pos = c - 65;
result *= PRIMES[pos];
}
return result;
}
private long time = 0L;
private void measureTime() {
long t = new Date().getTime();
if (time == 0L) {
time = t;
} else {
time = t - time;
}
}
}