Есть кубики. 6 штук. Есть русский алфавит. Граней суммарно у кубиков больше, чем букв в алфавите, но для простоты будем считать, что буквы дублировать нельзя, лишние грани оставим пустыми. Есть словарь русских слов.

Требуется разместить буквы на кубиках таким образом, чтобы была возможность составить из них наибольшее количество слов словаря.

(Вариант задачи 2) на пустых гранях можно разместить дубликаты любых букв.

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

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

во, нашел. Частотность, называется. https://ru.wikipedia.org/wiki/%D0%A7%D0%B0%D1%81%D1%82%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C

> kilkennycat ©   (19.09.16 22:59) [3]

там, на сколько я понял, про какой-то конкретный словарь речь. так что статистику самому надо будет высчитывать по этому словарю. + ну получим мы результат, как по ссылке. а вот как оттуда выудить идеальное решение - пока не знаю. ясное дело, что можно посчитать самые часто используемые гласные и согласные и про чередовать их, но это не идеальное решение.

> и ограничивая задачу шестью кубиками, мы серьёзно сокращаем словарь.

А от запрета дублировать буквы от словаря вообще, по моему, остаются одни ошметки.

Удалено модератором

Если достаточно найти близкое решение без доказательств, можно воспользоваться генетическим алгоритмом. Я так заполнял сложные сетки кроссвордов.

> Dimka Maslov ©   (19.09.16 21:53) [1]
>
> Можно придумать и третий вариант задачи - что бы ни при
> каких комбинациях кубиков не образовывались основополагающие
> слова великого и могучего.

Эту проблему решает наличие словаря, в котором можно изначально оставить только подходящие слова :)

> Eraser ©   (20.09.16 01:00) [4]
>
> > kilkennycat ©   (19.09.16 22:59) [3]
>
> там, на сколько я понял, про какой-то конкретный словарь
> речь.

Ну частотность можно и самостоятельно по словарю посчитать. Только не очень понятно что дальше с этой частотностью делать...

> DayGaykin ©   (20.09.16 10:40) [7]
>
> Если достаточно найти близкое решение без доказательств,
>  можно воспользоваться генетическим алгоритмом.

А как мы узнаем, близкое ли это решение?

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

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

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

> другое дело взять кубики с конкретной раскладкой и изменить
> ее чтобы у нее слов стало больше
>
>

Так возьми случайную раскладку и улучшай.


> > DayGaykin ©   (20.09.16 10:40) [7]
> >
> > Если достаточно найти близкое решение без доказательств,
>
> >  можно воспользоваться генетическим алгоритмом.
>
> А как мы узнаем, близкое ли это решение?

Никак. Если интуитивно тебе решение удовлетворяет - останавливаешь процесс поиска.
В моем случае задача была практическая, а этот способ дал хоть какое-то решение за короткое время, поэтому я на нем остановился.

Так возьми случайную раскладку и улучшай.

нахрена мне заниматься тупой работой?
сам улучшай.
никто не знает какое же наибольшее количество слов не длиннее 6 букв есть в русском.

> никто не знает какое же наибольшее количество слов не длиннее
> 6 букв есть в русском.

"Есть словарь русских слов"

есть. и што?

в нем все слова?

у меня был когда-то толстенный англо-русский на 80К слов.
И чо?

в вопросе-то было про слова языка а не слова из словаря.

> iop ©   (20.09.16 12:51) [16]
>
> в вопросе-то было про слова языка а не слова из словаря.

В вопросе было, дословно: "составить из них наибольшее количество слов словаря".

Ты скучен.

> Sergey13 ©   (20.09.16 08:30) [5]
> А от запрета дублировать буквы от словаря вообще, по моему, остаются одни ошметки.

как вариант,
потом в этих ошмётках считаем вероятность 'близости' буковок и рассыпаем буквы по кубиках так (не знаю как), чтобы средняя взаимовероятность ('вес кубиков') была одинакова

> А как мы узнаем, близкое ли это решение?

Так по условию большее, а не максимальное. Достаточно сравнить с другими результатами.

Я бы тоже использовал генетические алгоритмы.

А вообще профессор Зелезняк проболтался, что троек символов доступных для составления слов около 1 000. т.е. можно составить цепочки запрещенных к перебору и далее по ним отсекать.  Так что полный перебор на кластере возможен.