Когда я учился в школе, мне приходилось ездить каждый день на метро, начиная с 5 класса. Чтобы первым успевать к экскалатору или к переходу на другую ветку, я старался держаться около дверей вагона. В течении получаса передо мной маячила надпись Не прислоняться, написанная на каждой двери вагона московского метро. Сначала я смотрел на эту надпись снизу вверх, потом надпись была на уровне моих глаз, а когда заканчивал школу, то смотрел на нее уже свысока))). Чтобы не скучать, я придумал себе простое занятие — составлять слова из букв, входящих в эту надпись. Слова из трех или четырех букв придумать было достаточно просто: стол, слон, нос, сон, лот и т.п. Когда легкие слова закончились, я пытался найти уже более сложные слова. И испытывал радость, когда получалось составить какое-нибудь новое слово. Например, удалось найди шестибуквенные слова типа пистон, пионер. Были даже семибуквенные находки — престол. Позже, когда я увлекся программированием, я поймал себя на мысли — как было бы здорово написать программу, которая сама найдет все существующие варианты. Эта была моя детская мечта. Как хорошо было бы, если эту задачку предложили на олимпиаде для программистов. Хочется узнать все слова, зашифрованные в этой незамысловатой надписи. Как я себе представляю, эту задачу можно разделить на два этапа. Первый этап — комбинаторная задача, которая сводится к получению всех возможных перестановок букв. Вторая задача — сверка получившихся комбинаций с каким-то большим словарем, чтобы оставить только осмысленные слова. Вот такая у меня была детская забава.
Читать далее →