Задачка

← →
Kerk © (2016-09-19 19:26) [0]

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

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

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

← →
Dimka Maslov © (2016-09-19 21:53) [1]

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

← →
kilkennycat © (2016-09-19 22:55) [2]

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

← →
kilkennycat © (2016-09-19 22:59) [3]

во, нашел. Частотность, называется. 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

← →
Eraser © (2016-09-20 01:00) [4]

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

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

← →
Sergey13 © (2016-09-20 08:30) [5]

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

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

← →
iop © (2016-09-20 09:02) [6]

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

← →
DayGaykin © (2016-09-20 10:40) [7]

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

← →
Kerk © (2016-09-20 10:45) [8]

> 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]
>
> Если достаточно найти близкое решение без доказательств,
> можно воспользоваться генетическим алгоритмом.

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

← →
iop © (2016-09-20 11:46) [9]

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

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

← →
iop © (2016-09-20 11:53) [10]

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

← →
DayGaykin © (2016-09-20 11:59) [11]

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

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

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

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

← →
iop © (2016-09-20 12:12) [12]

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

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

← →
Kerk © (2016-09-20 12:15) [13]

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

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

← →
iop © (2016-09-20 12:49) [14]

есть. и што?

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

← →
iop © (2016-09-20 12:50) [15]

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

← →
iop © (2016-09-20 12:51) [16]

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

← →
Kerk © (2016-09-20 12:59) [17]

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

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

Ты скучен.

← →
NoUser © (2016-09-20 18:38) [18]

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

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

← →
Pavia © (2016-09-20 21:20) [19]

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

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

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

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

← →
Dimka Maslov © (2016-09-20 21:50) [20]

> Эту проблему решает наличие словаря

А вот и не решает, ибо что мешает из кубиков составлять не словарные слова? Мы так половину алфавита выкинем.

← →
Kipor © (2016-09-20 22:45) [21]

На основе словаря для каждой буквы посчитать вероятность встретить в одном слове другую букву.
вроде получится массив 32! элементов

Если в одном слове две буквы встречаются - вероятность их встречи плюс 1/X.
Где X - количество слов в словаре.

и так для каждого слова в словаре и каждой пары букв.

← →
Kipor © (2016-09-20 23:02) [22]

хотя всё сложнее :(

Кроме полного перебора не придумал решения.

← →
kilkennycat © (2016-09-21 03:39) [23]

> Kipor © (20.09.16 23:02) [22]

да. днем тож пришел к такому же выводу.

← →
kilkennycat © (2016-09-21 03:39) [24]

и решений будет несколько.

← →
Inovet © (2016-09-21 05:18) [25]

> [12] iop © (20.09.16 12:12)
> не длиннее 6 букв есть в русском

Я видел, но забыл. Напомнишь?

← →
Sha © (2016-09-21 09:54) [26]

> Кроме полного перебора не придумал решения.

Количество вариантов при полном переборе в int64 не влезет.
С учетом времени на оценку каждого варианта - жизни точно не хватит.

← →
Sha © (2016-09-21 10:17) [27]

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

Делим все буквы на 2 класса по 18 букв:
1 класс. Наиболее частые + наиболее редкие + 3 пустышки
2 класс. Буквы со средней частотой встречаемости.

Понятно, что таких разбиений несколько.
Для каждого из них мы найдем одно или несколько хороших решений.

Как ищем хорошее.
1. Сначала буквы первого класса разбрасываем по кубикам на основе их взаимной неприязни.
2. Затем для каждого полученного варианта проверяем 137.225.088.000 вариантов добавить буквы второго класса.
Думаю, это уже посчитать будет можно.

← →
Sha © (2016-09-21 10:58) [28]

Идея решения [27] в том, что перебираются только те варианты разбросать второй класс,
которые соответствуют только небольшому числу лучших вариантов разбросать первый класс.

я б начал с анализа морфологии заданного словаря: приставки, корни, суффиксы...

и в задаче не указано: интересуют только 6-буквенные слова?

> картман © (21.09.16 11:18) [29]

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

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

А запрета собирать слова из словаря 2 нет? например требование обяхательно разместить буквы "Й", "Х", "У" на одном кубике?

> Sha © (21.09.16 11:39) [30]

думаю, мое предложение упростит перебор:

выбрали самый частый корень
приставки
суффиксы
окончания

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

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

Не?

> Следующий по частотности корень.
>

ну, чуть сложнее

> картман © (21.09.16 12:24) [32]

чем конкретно помогают части слова,
если все то же самое можно проделать с целым словом
и получить более достоверный результат?

> картман © (21.09.16 12:24) [32]

Каждый кубик - множество, слово - множество.
Слово не представимо набором кубиков,
если пересекается хотя бы с одним кубиком более, чем двумя элементами.

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

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

6 букв на кубике - это 15 их пар, всего на 6 кубиках - 80 пар букв (считая без пустых).

пойдем по отсортированному по количеству нахождений списку пар от минимума по направлению к максимуму, строя граф полусовпадающих пар, пока он не поддастся разбиению на 6 частей по 15 ребер каждая.
(в алгоритмах графов не силен, но как-то так)

> если все то же самое можно проделать с целым словом
> и получить более достоверный результат?

более ли, учитывая предложенный в [27] алгоритм?

> картман © (21.09.16 14:17) [38]

по моим ощущениям - да )

Там фишка в том,
что и для класса среднечастотных букв будет выполнен полный перебор,
и для класса высокочастотных и низкочастотных - тоже полный.
Но раздельный. И раздел только один. Взаимное влияние минимально.

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

Конечно, все это мои ощущения, и все надо проверять.

[27] довольно легко программируется.
При наличии готового словаря - за один вечерок можно и результат получить.
Я бы разбивал буквы на 2 множества по 16 штук, без "ё" было бы проще.

А другие варианты пока только в теории )

> что самое страшное, взаимное влияние этих разделов никак
> не учитывается,

да, увы(

Задачка Найти похожие ветки