Анаграмма

ЗАДАЧА "Anagram"

Составить программу ANAGRAM, которая:
1) вводит словарь (последовательность, состоящая из N слов
  (N<=2000)), длина слов в котором не превосходит 20 символов,
  из текстового ASCII-файла, имя которого задано
  первым параметром командной строки;
2) находит в словаре все анаграммы (слова одинаковой длины,
  составленные из одних и тех же букв);
3) выводит в результирующий текстовый ASCII-файл,
  имя которого задано вторым параметром командной строки,
  списки всех анаграмм по одному списку в строке.

Пример

Исходный файл:                    Результирующий файл:

САЛАТ                             АТЛАС САЛАТ
БАЛОК                             БАЛОК БОКАЛ КОЛБА
РАКЕТА                            РАКЕТА КАРЕТА КАРАТЕ
ОКЛАД                             ОКЛАД ЛОДКА
ЛОДКА                             ТОР РОТ
БОКАЛ
АТЛАС
КОЛБА
КАРЕТА
ТОР
РОТ
КАРАТЕ



Затруднение вызывает именно поиск анаграм, если в слове больше 2х одинаковых букв...
Помогите, а?..
мыльте на second_box@mail.ru

Смотри, например, Джон Бентли "Жемчужины программирования" 2-ое издание.
Каждому слову можно поставить в соответствие ключ, который получается из этого слова если все буквы в нем расположить в алфавитном порядке.
Например ключем слов САЛАТ и АТЛАС будет "ААЛСТ" - у слов анаграмм ключи совпадают. Теперь тебе нужно только отсортировать все слова по их ключам. Слова анаграммы окажутся рядом друг с другом. Так ты их все и найдешь...

Цитата S.Yu.Gubanov, 14.05.03, 10:14:38

Смотри, например, Джон Бентли "Жемчужины программирования" 2-ое издание.
Каждому слову можно поставить в соответствие ключ, который получается из этого слова если все буквы в нем расположить в алфавитном порядке.
Например ключем слов САЛАТ и АТЛАС будет "ААЛСТ" - у слов анаграмм ключи совпадают. Теперь тебе нужно только отсортировать все слова по их ключам. Слова анаграммы окажутся рядом друг с другом. Так ты их все и найдешь...

Бентля конечно молодец вот только кол-во
ключей будет 33 встепени 8 =2 в степени 40
кажется не разумным

Можно предварительно в качестве дополнительного ключа использовать сумму всех символов слова. Произвести сортировку слов. И слова подозрительные на анаграммы, будут уже рядом. А затем уже смотреть и по буквенному ключу слова...

Чтобы программа отработала быстрее, сначала сортировать слова по длинне, а после записи анаграмм определенной длинны слов выкинуть все строки этой длинны. Создавать ключи мне кажется также неэффективно. Сначала нужно просуммировать символы как байты. Быстро отпадет большое количество ненужных вариантов. В случае, если суммаа байтов совпала переходить к проверке нужного количества соответствующих байтов в том и другом случае по счетчикам.

Именно об этом и шла речь ;D

Цитата esperanto, 14.05.03, 10:59:48

Бентля конечно молодец вот только кол-во
ключей будет 33 встепени 8 =2 в степени 40
кажется не разумным

Не въезжаю - как же это, раз слов меньше 2000, и каждому слову по одному ключу, то откуда берутся 2^40 ключей?

Ведь для слова ключ определяется однозначно сортировкой его букв.

Можно сделать в один проход: создать динамический двухмерный массив - в одном направлении новае анаграммы, в другом совпадающие.

Подсчитать все буквы и сверить в каждом слове кол-во.

На Паскале:
Если проблема только с проверкой слов на анограммы то может это поможет:
Проверка 2х слов на анограммы.

var s1,s2:string; <br>    i:integer; <br>    f:boolean; <br>    ch:char; <br>    b1,b2:array['А'..'Я'] of integer; <br>begin <br>     for ch:='А' to 'Я' do <br>     begin <br>          b1[ch]:=0; <br>          b2[ch]:=0; <br>     end; <br>     readln(s1); <br>     readln(s2); <br>     for i:=1 to length(s1) do <br>     inc(b1[s1[i]]); <br>     for i:=1 to length(s2) do <br>     inc(b2[s2[i]]); <br>     f:=true; <br>     for ch:='А' to 'Я' do <br>     if b1[ch]<>b2[ch] then f:=false; <br>     if f then writeln('Анограмма') <br>     else writeln('Нет'); <br>     readln; <br>end.

P.s. СМ. http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi?board=pascal;action=display;num=1052838115
Зачем поднимать вопрос в 2-х темах??

Сообщение отредактировано: @Hgpeu - 15.05.03, 02:34