Однажды я ехал на работу и, направляясь к выходу из вагона, вдруг вспомнил, как в младшей школе нам надо было составить как можно больше слов из букв, входящих в слово «гастроном». Было весело: помнится, я целый вечер сидел и увлеченно составлял всё новые слова, удивляясь, как их много. Примерно через десять лет после этого, когда я уже был на втором курсе, несколько моих одногруппников озадачилось двумя вопросами:
1) Чем заняться на очень скучных лекциях по операционным системам?
2) Какое слово можно взять вместо «гастроном», чтобы из него можно было составить как можно больше других слов?
Вооружившись ручками и бумагой, путём перебора (в неделю было две лекции по операционным системам, так что времени хватало) было выявлено слово «банкоматостроение», из которого усилиями примерно четырёх-шести человек было составлено более двухсот слов.
Выходя из вагона на платформу, я твёрдо решил попытаться ответить на второй вопрос, делегировав пересчёт слов машине.
258 строк на питоне и заранее подготовленный список слов всё решили. Как это было сделано, будет описано в конце поста, пока же скажем о базе слов, которые участвовали в процессе: это всё общеупотребительные существительные, нарицательные, единственное число, именительный падеж, всего 22049 (двадцать две тысячи сорок девять) штук. «Общеупотребительные» --- в том смысле, что не были использованы специфичные существительные вроде названий химических соединений (акрилонитрилбутадиенстерол!).
А теперь --- результаты.
Я начал со слова «гастроном». Посидев-потупив маленько, я составил из него 39 слов. Их можно представить списком. А именно:
астроном
агроном
гном
гонор
гора
гром
грот
маг
мат
матрос
монстр
мор
мот
морг
морс
нога
нора
нота
ор
оса
острог
рог
рога
ром
роман
роса
рост
рота
сом
сон
сонм
сорт
стан
стог
стон
сторона
торг
трон
трос
Кроме того, по ним можно нарисовать схему схему:
, что мне кажется более забавным, и, может быть, это в чём-то нагляднее.
Программа же, в отличие от безграмотного меня, составила 96 слов (список Список:
агроном
ар
арго
аргон
арт
ас
астроном
атом
гам
гарсон
гном
го
гомон
гон
гонор
гора
гормон
горн
гот
гран
грант
гром
грот
маг
манго
манто
март
масон
мат
матрос
монстр
мор
морг
морс
мост
мотор
нарост
наст
но
нога
нора
норма
нос
нота
ом
омар
ор
орган
оса
осман
осмотр
ост
острог
острога
отрог
ранг
ро
рог
ром
роман
романс
роно
роса
рост
рот
рота
самогон
сан
смог
смотр
сом
сома
сон
сонм
сор
сорт
сота
срам
стан
стог
стон
сторона
танго
таро
тога
том
тон
тор
тора
торг
торос
торс
транс
трон
трос
). Для них схема выглядит уже гораздо замысловатее. вот так:
Уже после этого примера мой личный словарный запас обогатился. обогатился такими словами:
- ар --- оказывается, это такая единица площади, равная площади квадрата со стороной в 10 метров.
- арго --- согласно википедии, «язык какой-либо социально замкнутой группы лиц, характеризующийся специфичностью используемой лексики, своеобразием её употребления, но не имеющий собственной фонетической и грамматической системы.» И никакого отношения к аргонавтам это слово не имеет.
- манто --- такой вид пальто. Признаться, поначалу я подумал, что так называется реакция человека на манту. Или единственное число слова «манты».
- но --- не только предлог и доктор, но и вид японского театра.
- ро --- оказывается, названия греческих букв входят в русский язык как имена нарицательные. Кроме того, был еще такой искусственный язык.
- сома --- ритуальный напиток у индоиранцев.
- тора --- оказывается, это не только часть библии, а вообще совокупность понимания иудейского традиционного закона, и, следовательно, имя нарицательное.
Теперь же --- топ-10 лучших слов для составления новых слов! В виде таблички.
| Место | Слово | Число слов, которые можно составить |
| 1 | предпринимательство | 1287 |
| 2 | привлекательность | 1196 |
| 3 | достопримечательность | 1190 |
| 4 | гидроэлектростанция | 1167 |
| 5 | металлоконструкция | 1165 |
| 6 | телерадиокомпания | 1152 |
| 7 | благоприятствование | 1142 |
| 8 | авиапромышленность | 1102 |
| 9 | разгосударствление | 1033 |
| 10 | экспериментирование | 989 |
Для интересующихся --- список слов, которых можно получить из букв слова « предпринимательство». Их много и они под катом!
авто
автор
ад
адвентист
адепт
адрес
аи
аир
аист
альпинист
альт
альтист
амвон
аметист
амин
ампер
ампир
анис
анод
антимир
антипод
антисемит
антитело
антресоли
апельсин
аперитив
аппетит
апрель
ар
арест
арт
артель
артист
артрит
ас
аспид
аспирин
астероид
атеист
ателье
атлет
атом
вал
валет
вальс
вампир
ваниль
вар
варенье
варьете
ватт
ведро
ведьма
веер
велосипед
вена
вентиль
вепрь
вера
верность
верста
вертел
вертеп
вертолет
вес
весло
весна
вест
вестерн
весть
весь
ветер
ветеран
ветеринар
ветла
вето
ветрило
вид
видение
виденье
видео
видимость
вина
винил
вино
винодел
виноделие
винт
виола
вирион
вис
витамин
витрина
владение
власть
вода
водила
водитель
воин
воитель
вол
волан
волна
вольер
вольера
вольт
вольтметр
вонь
вопль
вор
ворс
ворье
воспаление
воспитание
воспитатель
впадение
враль
вранье
вред
вредитель
вредность
втора
давление
давность
даль
дан
дантист
дань
даос
дар
дарение
даритель
дартс
дверь
двор
дева
деверь
делание
делимость
дело
дельта
демон
день
депо
дер
дерево
дерен
дерма
дерматин
дерматит
дерн
дерьмо
десант
десерт
десна
деспот
деталь
детвора
детина
детство
диавол
диаметр
диамин
дива
диван
диверсант
дивертисмент
диво
диета
дилер
дилетант
динамит
динамо
динар
диплом
дипломант
дипломат
диполь
диспаритет
дите
длань
длина
дно
до
доверие
доверитель
дол
долина
дольмен
дом
домен
домина
домна
дон
дона
досье
дот
драп
древесина
древние
древность
древо
дрель
дрема
дремота
дрова
дровни
евро
еда
единство
елань
ель
енот
ер
ересь
ива
иврит
идеал
идеалист
идиома
идиот
идол
иена
ил
имение
имитатор
императив
император
империал
имплант
импорт
импортер
импотент
импресарио
инвалид
инвертор
инвестор
инет
интервал
интерес
интерьер
интим
интроверт
инь
иод
ион
ирис
ирмос
ирод
ислам
испарение
испаритель
исповедание
исповедь
испод
исподнее
исполин
исправление
истина
истмат
истома
лавр
лад
ладонь
ландо
лань
лапоть
ларь
ласт
лат
лев
левит
лево
лед
леди
леер
лен
лендровер
леность
лента
лень
леопард
лепет
лепта
лес
леса
лесина
лесть
лет
лета
лето
летопись
ливень
ливер
лидер
лидерство
лиман
лимит
лимон
лимонад
линь
липа
липид
лира
лис
лиса
лист
листва
листопад
литвин
литер
литера
литератор
литр
литье
лов
лом
лопасть
лор
лорд
лори
лорнет
лось
лот
льдина
мавр
маловер
малое
малость
маневр
манер
манси
манто
маньерист
марево
мари
марлин
мародер
март
мартен
мартини
марь
масло
масон
мастер
мастит
масть
мат
материнство
матерь
матрос
мать
мед
медалист
медаль
медальон
медиа
медиатор
медперсонал
медь
мел
мель
мена
мент
ментол
ментор
мера
меридиан
мерило
мерин
мерс
месиво
место
месть
месье
мета
метан
метание
метанол
метель
метеор
метеорит
метис
метла
метод
метода
методист
метр
метрдотель
метро
миледи
милорд
милосердие
милость
мильон
мина
минарет
миндаль
минер
минерал
минет
министр
минор
мир
миро
мироед
мирра
мирт
мистер
митра
мова
мода
модель
модельер
модерн
модернист
мол
молва
моление
молитва
моль
монета
монстр
монтер
мопед
мопс
мор
моралист
мораль
морда
мордва
море
морс
мост
мосье
мотель
мотив
мститель
мсье
навес
навет
надел
надлом
надпись
наем
наитие
нал
наледь
налет
налив
налим
напев
напор
нардеп
народ
нарост
насилие
наследие
наст
настил
невеста
невидаль
невидимость
невод
недотепа
недра
нелепость
нельма
немилость
немота
неолит
непоседа
нерадивость
нерв
нерест
нерпа
нет
нетерпимость
нива
нитрат
нитрид
нитрит
нить
но
новь
ноль
номер
нора
норд
норма
нормаль
норматив
нос
носитель
нота
нрав
овал
овен
овес
овин
овладение
ода
одевание
одр
олеандр
олень
олива
оливье
ом
омар
омела
омлет
опад
опал
опасение
опер
опера
оперетта
опиат
описание
опись
опт
оптимист
ор
орда
орден
ордер
орел
ориентир
оса
осветитель
оседание
осел
осень
осетин
осетр
осетрина
осина
осман
оспа
оспина
ост
оставление
острие
ость
ось
отвал
отвар
отверстие
отвес
ответ
отдаление
отдание
отдел
отел
отель
отит
отлет
отлив
отмель
отмена
отметина
отмирание
отпад
отпадение
отпевание
отправитель
отправление
отравитель
отравление
отрасль
отсвет
отсев
отстрел
оттепель
па
павильон
павлин
падение
падло
пал
пальто
памперс
пан
панель
пани
паперть
пар
пардон
парение
парень
пари
паритет
парность
пародист
пароль
паром
паротит
партер
партнер
партнерство
пас
паспорт
пастель
пастор
пасть
пат
патент
патер
патио
патриот
патрон
педаль
педант
педераст
педиатр
педсовет
пелена
пелерина
пена
пенал
пенальти
пение
пенис
пенопласт
пенс
пень
пенье
пепел
пепси
пептид
первое
перевал
перевод
перед
перелив
перелом
перенос
перепад
перепись
пересмотр
перила
периметр
перина
период
перитонит
перл
пернатое
перо
перрон
перс
персептрон
перси
персона
персонал
перст
перстень
пес
песнь
пестрота
петит
пи
пианист
пиар
пиастр
пиво
пидор
пиетет
пиит
пила
пилон
пилот
пим
пион
пионер
пипл
пир
пирамидон
пират
пиратство
пирит
пирс
писание
писарь
писатель
пистолет
пистон
письмена
письмо
питание
питие
питон
питье
плав
плавень
плавность
пламень
план
планер
пласт
пластит
плат
платиноид
платность
плато
платье
плева
плевра
плеврит
плед
плеер
плен
плес
плесень
плетень
плеть
плита
плов
плод
плот
плотва
плотина
плоттер
плоть
повар
поверье
повеса
повесть
поветрие
поветь
под
подавление
податель
подать
подвал
подвес
подлет
подлива
подмастерье
подмена
подписание
подписант
подпись
подпитие
подтип
поедание
пол
пола
полати
полведра
полдень
поле
полесье
полет
полиамид
полиартрит
полив
полимер
полип
полис
полисмен
политес
полметра
полмира
полпред
полтина
поместье
помесь
помет
помета
помин
помпа
пони
понт
поп
попа
попрание
попса
пора
порт
портал
портер
портрет
портье
портьера
посад
посев
посетитель
послание
посрамление
пост
постамент
постель
постер
пот
праведность
правило
правитель
правление
право
правоприменитель
прапор
прародитель
прево
превратность
предание
преданье
предатель
предательство
предел
предисловие
предмет
предметность
предписание
предприниматель
представитель
преемство
прелесть
прель
премирование
премьер
премьера
премьерство
препирательство
препод
препона
пресвитер
престол
привал
привес
привет
привод
придание
приданое
придел
прием
прилет
прилив
прима
примат
пример
примесь
примета
принтер
приоритет
припас
припев
приплод
природа
прирост
присвоение
приседание
присловье
присмотр
пристав
пристань
притвор
притон
притоп
провал
провиант
провидение
продление
проем
пролет
пролив
променад
пропан
пропасть
пропись
пропитание
прорва
просвет
просветитель
проседь
проситель
простирание
прострел
протеин
протест
противень
псалом
псалтирь
псевдоним
псина
пьедестал
пьеса
рав
равелин
радение
радетель
радио
радист
радон
радость
ранимость
рантье
рань
рапид
рапорт
раритет
распев
распитие
раствор
растворение
растворитель
растение
растление
рать
рвань
рванье
рвение
рвота
рдест
ре
реал
реалист
рев
ревень
реверанс
реверс
ревнитель
ревность
редис
реестр
реле
рельс
рема
ремень
ремесло
ремонт
реноме
рента
реостат
репа
репетитор
ресторан
ретинол
реторта
ретро
ридостин
рис
рисование
ритм
ро
ров
род
родина
родитель
родстер
роль
ром
роман
романист
романс
роса
рост
рот
рота
ротмистр
сад
сало
салон
сальдо
сальто
самоед
самолет
сан
сани
сантиметр
сап
сапер
сари
сатин
сатир
свами
сван
сват
сверло
свет
светило
светотень
свидание
свиданье
свидетель
свирель
свита
свитер
свод
свора
сев
север
седан
седина
седло
седловина
селен
селитра
село
сель
сельва
сельпо
семинар
семит
сенат
сенатор
сени
сено
сеновал
сень
сеньор
сеньора
сеньорита
сера
сервант
сервелат
сервер
середа
середина
сериал
серотип
серп
сет
сетование
сеттер
сеть
си
сидение
сидень
сиденье
сидор
сиена
сила
силен
символ
синдром
синева
синод
синь
синьор
синьора
сип
сир
сирена
сирень
сироп
сирота
сити
сито
ситро
след
следование
слепень
слепота
слет
слив
слива
словарь
слом
слон
слот
смена
смерд
смерть
смета
смирение
смола
смоль
смотр
смотрение
смотритель
смрад
снедь
сноп
сова
совет
совпадение
сода
соитие
солдат
соление
соленье
соль
сом
сома
сон
сонет
сонм
сопение
сопли
сор
сорт
сортамент
сортимент
сортир
сота
спа
спад
спам
спаниель
спанье
сперма
спидометр
спин
спина
спираль
спирт
спиртное
сплав
сплин
спор
спора
спорт
спринт
спринтер
срам
среда
средина
ставень
стадион
стадо
сталь
стан
стапель
старение
старовер
старое
старпом
старт
стартер
старье
стать
ствол
створ
стела
стена
стенд
степ
степень
степь
стерва
стереотип
стилет
стиль
стипендиат
стирание
стол
столетие
столетье
столп
стон
стопа
стопарь
стрела
стрема
стрит
строение
строитель
строп
стропа
тавро
таинство
талес
талон
таль
тампон
тандем
тапер
таро
тать
тварность
тварь
твердость
твердь
твид
твин
твист
творение
творенье
театр
театровед
телемост
телепат
телеса
тело
тема
темень
темнота
темп
темь
тендер
тенета
тенор
тент
тень
теорема
тепло
теплосеть
теплота
терапевт
терем
терм
термин
терминал
терминатор
термит
термос
терние
терпимость
терьер
тес
теснота
тест
тестирование
тесто
тесть
тесьма
тетива
тетрадь
тетрис
тина
тип
тир
тиран
тиранство
тире
титан
титр
титрование
тлен
тление
тмин
товар
тол
толпа
толь
том
томат
томление
тон
топ
топтание
топь
тор
тора
тори
торпеда
торс
торт
тост
тостер
тотем
травление
трал
трамплин
транс
транслит
транспорт
трап
траст
трель
тремор
тренд
тренер
трение
треп
трепет
трепло
трест
треста
треть
третье
триединство
триместр
трио
триплет
триппер
трипсин
тритон
трон
троп
тропа
тропарь
трос
трость
тротил
тьма
Можно модифицировать вопрос и искать самое «плодовитое» слово не среди всех слов, а среди всех слов заданное длинны. Результаты будут такие. (в получившейся базе слов не было слов в 23 буквы, увы):
| Число букв в слове | Сколько слов можно составить | Число максимальных слов | Пример слова |
| 3 | 4 | 9 | мор, род, пас, пэр |
| 4 | 10 | 3 | брак, барк, краб, дрок, корд |
| 5 | 24 | 1 | актор |
| 6 | 49 | 2 | прокат, тропка |
| 7 | 86 | 1 | простак |
| 8 | 141 | 1 | соратник |
| 9 | 227 | 1 | клипсатор |
| 10 | 308 | 1 | крестовина |
| 11 | 447 | 1 | сотрапезник |
| 12 | 556 | 1 | консерватизм |
| 13 | 630 | 1 | автоинспектор |
| 14 | 652 | 1 | декоративность |
| 15 | 807 | 1 | государственник |
| 16 | 941 | 1 | контрнаступление |
| 17 | 1196 | 1 | привлекательность |
| 18 | 1165 | 1 | металлоконструкция |
| 19 | 1287 | 1 | предпринимательство |
| 20 | 950 | 1 | режиссер-постановщик |
| 21 | 1190 | 1 | достопримечательность |
| 22 | 573 | 1 | самоусовершенствование |
| 23 | - | - | - |
| 24 | 864 | 1 | высокопревосходительство |
Попутно я подумал --- а из какого слова можно составить больше всего слов, используя все его буквы, т. е. ничего не выкидывая? Оказывается, из таких: автор, втора, отвар, рвота, тавро, товар. Иными словами, из любого из этих шести слов (по пять букв) можно составить любое другое простой перестановкой букв.
(Да, в русском языке есть слово «втора». Толковый словарь Даля говорит про слово него: ЧУДО, диковина, небывальщина, задача; | вздор, чепуха, небылица. | случай, беда, напасть, притка, притча, неудача, помеха. если слово это от вторья (отголоска), то знач., что отозвалось худым. употребл. более в восклицаниях. эка втора вторуща, ветер окно расшиб! эку втору занес! вишь, кака втора сталась!)
И, под конец --- ещё несколько схем выводимых слов (я люблю схемы!).
Математика, 30 слов. Математика, 30 слов:
Прокат, 49 слов. Прокат (49 слов):
Бензопила, 52 слова. Бензопила (52 слова):
Океанология, 69 слов. Океанология, 69 слов:
Кроманьонец, 81 слово. Кроманьонец, 81 слово:
Теперь --- как оно делалось.
Сначала был подготовлен «список всех существительных в русском языке» (точнее, что-то, что к нему очень близко). Для этого я использовал «Частотный словарь современного русского языка» (О. Н. Ляшевская, С. А. Шаров, М.: Азбуковник, 2009), доступный в виде текстового файла тут. Как уже было сказано, в этом словаре есть 22049 существительных. (Вообще, это довольно важный вопрос: я не хотел, чтобы в этом списке были имена собственные, междометия или аббревиатуры. Большинство интернет-сервисов, кстати, которые занимаются подобными соответствиями, считают аббревиатуры словами.)
После составления этого списка был построен специальный граф по следующим правилам.
Пусть запись «А → Б» означает «из букв слова А можно составить слово Б». Если А → Б и Б → А, то это означает, что слова А и Б состоят из одних и тех же букв (например, «ток» и «кот», или «топка» и «капот»). В таком случае будем говорить, что А и Б образуют одну лексему. Построим по исходному списку слов минимальный список лексем. (Минимальный в том смысле, что все возможные слова из списка «схлопываются» в соответствующие непересекающиеся лексемы).
Теперь из полученного списка лексем построим граф по следующим правилам:
1) Вершины графа --- лексемы.
2) Лексема А соединена с лексемой Б направленным ребром из А в Б тогда и только тогда, когда А → Б и не существует такой лексемы В, что А → В, В → Б.
Такой граф обладает рядом замечательных свойств: в нём нет петель и циклов, и, значит, его просто обходить. Строился он тоже просто: сначала в него вносились все лексемы из двух букв, потом --- из трёх, и так далее; при добавлении новой лексемы из n букв сначала просматривались все лексемы длиной n-1 букв, n-2 и так далее, исключая из рассмотрения те лексемы, что можно получить из ранее просмотренных.
Собственно, все «схемы выводимости» в посте --- подграфы этого графа.
На построение графа ушло порядка 45 минут, зато на все операции с ним (составление схем выводимости, например, или поиск самого «продуктивного» слова) уходило не более секунды. В графе 21413 вершин (лексем) и 204184 рёбер. На диске в бинарном виде он занимает 9.9 мегабайт.
Наконец, записанный в формате tgf граф подавался на вход программке yEd, которая в два клика делала из него красивую .png картинку.
На какую же ерунду я перевожу время, ох.