Головна сторінка
Top.Mail.Ru Яндекс.Метрика
Форум: "Інше";
Поточний архів: 2018.09.09;
Завантажити: [xml.tar.bz2];

Вниз

завдання Знайти схожі гілки


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]

*) Порахуємо для кожної пари букв число її знаходжень в словах словника і відсортуємо список не по спадаючій, а по зростанню



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 підкинув проблему і пішов :)

її ідеальне рішення - якщо не ідеальний архіватор, то вірний шлях до його створення)



kilkennycat ©   (2016-09-26 00:39) [60]


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

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



Sha ©   (2016-09-26 01:23) [61]

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

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



kilkennycat ©   (2016-09-26 01:29) [62]


> Sha © (26.09.16 01: 23) [61]

а е?



Sha ©   (2016-09-26 07:44) [63]

> Kilkennycat © (26.09.16 01: 29) [62]

е = е



kilkennycat ©   (2016-09-26 08:21) [64]


> Sha © (26.09.16 07: 44) [63]

взагалі то ні.



kilkennycat ©   (2016-09-26 08:21) [65]


> Sha © (26.09.16 07: 44) [63]

взагалі то ні.



Sha ©   (2016-09-26 09:17) [66]

але я так бачу)



Kerk ©   (2016-09-26 11:35) [67]


> Sha © (26.09.16 01: 23) [61]

Це за спрощеним варіантом [27]?



Sha ©   (2016-09-26 12:14) [68]

Kerk © (26.09.16 11: 35) [67]

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



сторінки: 1 2 вся гілка

Форум: "Інше";
Поточний архів: 2018.09.09;
Завантажити: [xml.tar.bz2];

Вгору





Пам'ять: 0.84 MB
Час: 0.044 c
8-1241286940
anonimos
2009-05-02 21:55
2018.09.09
Розумієте зображення


15-1474302374
церква
2016-09-19 19:26
2018.09.09
завдання





африкаанс албанський арабська вірменин азербайджанець баскський білоруський болгарська каталонський Китайська (спрощене письмо) Китайський традиційний) хорватський чеська данську мову нідерландський Ukranian естонець Філіппінська фінську мову французький
галісійська грузинський німецький грецький гаїтянський креольський давньоєврейську хінді угорський ісландський індонезієць ірландський італійський японський корейський латиська литовець македонець малайський мальтійський норвежець
перс полірування португальська румунський російська сербський словацький словенський іспанська суахілі шведську мову тайський турецька український урду в'єтнамський валлійський ідиш бенгальський боснійський
кебуано есперанто гуджараті хауса хмонг ігбо яванський каннада кхмерская Лао латинь маорі маратхі монгольський непальська панджабі сомалійський тамільська телугу йоруба
зулуський
Англійська Французький Німецький Італійський Португальська Русский Іспанська