Задачка

← →
картман © (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]

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

← →
Sha © (2016-09-22 20:42) [48]

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

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

← →
kilkennycat © (2016-09-22 21:12) [49]

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

← →
L_G © (2016-09-22 21:20) [50]

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

← →
Sha © (2016-09-22 21:35) [51]

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

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

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

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

← →
L_G © (2016-09-22 21:58) [52]

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

← →
manaka © (2016-09-22 23:39) [53]

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

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

← →
kilkennycat © (2016-09-23 02:08) [54]

> manaka © (22.09.16 23:39) [53]

возьмите алфавит до 1917 года, там от 35 до 37 букв :)

← →
SergP © (2016-09-23 13:31) [55]

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

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

← →
Kipor © (2016-09-24 23:12) [56]

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

← →
kilkennycat © (2016-09-25 01:37) [57]

> Kipor © (24.09.16 23:12) [56]

только не говори, что уже три дня не ешь, не пьешь, играешь в кубики :)

← →
L_G © (2016-09-25 09:44) [58]

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

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

← →
Eraser © (2016-09-25 22:23) [59]

> 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 вариантов снова берем лучшие, и т.д.
Алгоритм довольно быстро сходится.

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