Задачка

← →
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] в том, что перебираются только те варианты разбросать второй класс,
которые соответствуют только небольшому числу лучших вариантов разбросать первый класс.

← →
картман © (2016-09-21 11:18) [29]

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

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

← →
Sha © (2016-09-21 11:39) [30]

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

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

← →
Павел Калугин © (2016-09-21 11:41) [31]

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

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

← →
картман © (2016-09-21 12:24) [32]

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

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

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

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

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

Не?

← →
картман © (2016-09-21 12:25) [33]

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

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

← →
Inovet © (2016-09-21 12:58) [34]

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

Не. Слова, где в "машинах дышит интеграл", - скукота, пардон.

← →
Sha © (2016-09-21 13:23) [35]

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

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

← →
Sha © (2016-09-21 13:27) [36]

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

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

← →
L_G © (2016-09-21 13:57) [37]

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

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

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

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

← →
картман © (2016-09-21 14:17) [38]

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

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

← →
Sha © (2016-09-21 14:48) [39]

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

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

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

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

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

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

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

← →
картман © (2016-09-21 15:02) [40]

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

да, увы(

← →
kilkennycat © (2016-09-21 17:13) [41]

> Sha © (21.09.16 09:54) [26]

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

а ты посчитал все комбинации, или с учетом того, что слов в словаре не более, например, 1000?

← →
Sha © (2016-09-21 17:41) [42]

> kilkennycat © (21.09.16 17:13) [41]

Все комбинации, исходя из первоначальной постановки задачи:
36! / ( 6 * (6!)^7 )

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

> kilkennycat © (21.09.16 17:13) [41]

Это оценка снизу, она ближе к точному значению,
чем оценка сверху (без множителя 6 в знаменателе)

← →
kilkennycat © (2016-09-22 17:05) [44]

> Sha © (21.09.16 17:41) [42]

ну, это же все варианты... даже "абвгде"

← →
Sha © (2016-09-22 19:21) [45]

> kilkennycat © (22.09.16 17:05) [44]

это варианты не слов, а букв на кубиках,
и поэтому там можно написать даже "абвгде".

← →
L_G © (2016-09-22 20:31) [46]

подумал еще. надеюсь, получится описать алгоритм достаточно подробно.

на 6 гранях 6 кубиков у нас 36 букв (пусть 3 из них - пустышки),
их возможных сочетаний по 2 (пар) будет n!/(m!(n!-m!)) = n(n-1)/2 = 36*35/2 = 630

каждая пара букв, встречающаяся в словах словаря N раз, при размещении её на одном кубике уменьшит на N число слов, которые мы сможем составить из набора кубиков

посчитаем для каждой пары букв число её нахождений в словах словаря и отсортируем список по убыванию (первыми явно будут 3*35 пар с одной или двумя пустышками с нулевой суммой нахождений)

на каждом кубике у нас по 6*5/2 = 15 пар букв, на 6 кубиках - 80 пар

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

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

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

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

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

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

ну что, похоже, так уже гарантированно лучшее решение получится найти,
как думаете?

← →
L_G © (2016-09-22 20:35) [47]

*) посчитаем для каждой пары букв число её нахождений в словах словаря и отсортируем список не по убыванию, а по возрастанию

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

Пока неясно, откуда это следует.

надо идти с конца. сначала составить словарь.

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

> L_G © (22.09.16 21:20) [50]

Абсолютно неверно.

Оптимальное в целом решение не получается
как сумма частичных условных оптимальных решений на отдельных шагах.

Грубо говоря, можно съесть ферзя, но следующим ходом получить мат.

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

> Есть кубики. 6 штук. Есть русский алфавит.

Граней 36. букв 33. Всего три грани на дубли букв.
А в словаре есть "мама", "долото", "молоко" и т.д. И таких много.
Слова с повторяющимися буквами серьезно портят задачку...

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

А не 32*31 разве?

Kerk подкинул проблему и удалился :)

еще пара идеек:
1) модификация моего алгоритма с рассмотрением не пар, а троек букв наверняка даст лучшее решение
всего троек 36!/((36!-3!)3!) = 36*35*34/6 = 7140
подсчет отменяемых слов для троек, конечно, побольше времени займет,
зато подбор кубиков наверняка будет быстрее, чем с парами

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

> Kipor © (24.09.16 23:12) [56]
> Kerk подкинул проблему и удалился :)

её идеальное решение - если не идеальный архиватор, то верный путь к его созданию )

> Eraser © (25.09.16 22:23) [59]
>
> идеальный архиватор

возможно, я уже рассказывал про идеальный архиватор:
как-то давно, на одной работе подходит сотрудник компании, и говорит, что изобрел идеальный архиватор. Мне лишь программку остается написать. Суть изобретения: если архиватор сжимает в 2 раза, то многократное сжатие доведет файл до байта (ну или до бита). Когда я ему разъяснил, что вариантов байта не так уж много (а бита и подавно), и что согласно его теории получается, что в двух битах содержится Абсолютно Вся Информация и надо лишь создать Разархиватор, чувак начал думать над разархиватором.

У меня вот такие буковки на кубиках получаются на урезанном словаре Лопатина:

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

но я так вижу )

Kerk © (26.09.16 11:35) [67]

Гораздо проще оказалось искать решение алгоритмом вроде генетического.
На каждом шаге отбираем V лучших вариантов.
Для каждый из них производим M мутаций представляющих собой 1..16 перестановок букв.
Среди получившихся V*M вариантов снова берем лучшие, и т.д.
Алгоритм довольно быстро сходится.

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