PHP: ищем в словаре слова-анаграммы нужной длины

По самому простому определению, анаграмма получается из другого слова перестановкой его букв (рост-сорт-трос, апельсин-спаниель и т.д.)

Напишем небольшой скрипт, находящий в тексте анаграммы заданной в символах длины (не все подряд, чтобы не получалось слишком много результатов).

Использованный алгоритм - "лобовой", он сильно избыточен и не претендует на оптимальное быстродействие, но хорошо показывает, как на PHP удобно решать такие задачи, если быстродействие не критично.

Ниже приведён полный исходник приложения с подробными комментариями. Чтобы его выполнить на своём компьютере, нужно установить локальный сервер и записать скрипт в его корневую папку, например, под именем anagram.php, затем скопировать в ту же папку развёрнутый из архива .zip словарь под именем words.txt и выполнить скрипт из любого браузера как http://localhost/anagram.php

<?php
$words = file ('words.txt',FILE_IGNORE_NEW_LINES); //прочитать файл в массив
$length = 0;
$search_length = 15; //нужная длина слов
$max_length = 0; //найдём максимальную длину слова в словаре
$count = 0; //количество слов в словаре
 
foreach ($words as $word) { //каждое слово
 $chars = str_split ($word); //разбить на символы
 sort ($chars); //и отсортировать их
 $chars = implode ('', $chars); //слить обратно в строку
 $length = strlen ($chars); //узнать её длину
 $anagrams[$length][$chars][] = $word; //и положить в индексированный массив
 $word_len = strlen($word); //смотрим длину слова
 if ($word_len > $max_length) $max_length = $word_len; //и сравниваем с максимальной
 $count++; //увеличиваем счётчик слов
}
krsort ($anagrams); //отсортировать массив по ключам

echo 'Anagram words length for search='.$search_length."<br>\n".
     'Maximum of word length='.$max_length."<br>\n".
     'Number of words in words.txt='.$count."<br>\n".
     "List of anagrams:<br>\n"; //вывели общую информацию
 
foreach ($anagrams as $anagram) { //смотрим массив анаграмм
 foreach ($anagram as $words) { //для каждой анаграммы
  if (count ($words) > 1) { //если она есть (больше одного слова из тех же букв)
   if (strlen ($words[0]) == $search_length) { //и у неё нужная длина,
    foreach ($words as $word) echo $word.' '; //то печатаем все слова
    echo "<br>\n"; //и переводы строки
   }
  }
 }
}
?>

Самая длинная анаграмма, которую я нашёл в своём словарике, имеет длину 15 символов и ответ единственен:

Anagram words length for search=15
Maximum of word length=29
Number of words in words.txt=69903
List of anagrams:
dactylopteridae pterodactylidae

А вот наборов 5-буквенных анаграмм - более 700 штук.

Вот сам файл английского словаря, который я использовал, его формат простейший (одна строка - одно слово). В файле около 70000 слов.

 Скачать словарь words.txt в архиве .zip (220 Кб)

С расположенным удалённо словарём (это стандартный unixdict.txt, он меньшего размера), задачу можно было решить и так:

<?php
$words = explode("\n", file_get_contents('http://wiki.puzzlers.org/pub/wordlists/unixdict.txt'));
foreach ($words as $word) {
 $chars = str_split($word);
 sort($chars);
 $anagram[implode($chars)][] = $word;
}
 
$best = max(array_map('count', $anagram));
foreach ($anagram as $ana)
 if (count($ana) == $best)
  print_r($ana);
?>

16.11.2017, 14:41 [3273 просмотра]