Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Поиск панграмм из произвольной базы слов в Excel макросом - Мир MS Excel

Регистрация · Логин: · Пароль: · · Забыли пароль?
  • Страница 1 из 1
  • 1
Модератор форума: _Boroda_, Manyasha, SLAVICK, китин  
Мир MS Excel » Вопросы и решения » Вопросы по VBA » Поиск панграмм из произвольной базы слов в Excel макросом (Макросы/Sub)
Поиск панграмм из произвольной базы слов в Excel макросом
magNstr_rYJIon Дата: Четверг, 12.01.2017, 20:51 | Сообщение № 1
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
ПРИВЕТСТВИЕ

-Бодрого..
-Не ври, мне, скоту!((

(анаграмма в стиле «тихо сам с собою я веду беседу»)

ВАЖНО

Просматривая профиль тов. Казанского на сайте programmersforum.ru, наткнулся на тему, в комментарии к которой он рекомендует автору (REztor) в случае размещения вопроса на разных форумах, информировать об этом на каждом из них. Отыскав в гугле все форумы, на которых REztor разместил свой вопрос (sql.ru, programmersforum.ru, cyberforum.ru, forum.oszone.net), я таки готов рискнуть и повторить его подвиг. По случаю банкета к вышеупомянутым форумам также присоединяются planetaexcel.ru и excelworld.ru. Ссылки на соответствующие темы:

http://www.sql.ru/forum/1245788/v-poiskah-pangramm-excel-vba
http://programmersforum.ru/showthread.php?t=302720
http://www.cyberforum.ru/vba/thread1899149.html
http://forum.oszone.net/thread-322702.html
http://www.planetaexcel.ru/forum....omoshch

КТО МЫ?

Все мы люди-человеки.

ЧЕГО МЫ ХОТИМ?

На входе имеем базу слов, на выходе – все возможные по условиям панграммы.

УСЛОВИЯ

1. Панграммы ищем для n букв (первостепенно – 33).
2. Все буквы в конечном наборе слов предложении встречаются ровно по 1 разу.
3. Исходная база содержит слова с повторяющимися буквами и/или всякими ненужными символами (какими конкретно – не известно).

МОЙ ВКЛАД

1. Нашел формулу массива для первоначальной сортировки базы:
Код
{=ИЛИ((ДЛСТР(A2)-ДЛСТР(ПОДСТАВИТЬ(СТРОЧН(A2);СИМВОЛ(СТРОКА($1:$255));"")))>1)}

Для слов с повторяющимися буквами выдает ИСТИНА. Далее сортируем, все строки с ИСТИНА в расход, оставляем одни только ЛОЖИ.

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

3. Подумал над алгоритмом для работы с результирующей базой.

ВОЗМОЖНЫЙ АЛГОРИТМ

1. Выводим все буквы слова функцией ПСТР.
2. Создаем двоичный код каждого слова функцией СЧЁТЕСЛИ.
3. Переводим в десятичную систему счисления, поочередно умножая на 2^m (m<33) и затем суммируя. Можно, конечно, объединить все 0 и 1 в громоздкое 33-ёхзначное число, которое потом перегнать функцией ДВВДЕС. Имеем столбец #1 с.. назовем это численной записью числа.
4. Сортируем базу слов по столбцу #1. Имеем численную запись чисел по возрастанию/убыванию.
5. Моя остановочка.

Дело за малым – научиться выделять из столбца #1 диапазон слов с разными буквами, сумма численных значений которых равна (2^33)-1 = 8589934591 (для 33-ёх букв, не говоря уже о количестве вариаций для 32, 31 и т.д.) :)

ЛЁД ТРОНУЛСЯ

Нашел такую весчь, называется подбор слагаемых под нужную сумму. Является частным случаем «задачи о рюкзаке». Наиболее оптимальные на мой беглый взгляд алгоритмы обитают тута (http://www.excelworld.ru/forum/10-5196-1). Вот если бы эту штуку как-то применить в нашей задаче. Описанный мною выше возможный алгоритм можно упростить до записи слов в двоичном коде. Далее:

1. Берем первое слово, сверяем с каждым на наличие одинаковых букв (единичек). Отбираем массив #1(1) слов с буквами, которых нет в нашем первом слове.
2. Берем первое слово из массива #1(1), сверяем с каждым из массива #1(1) на наличие одинаковых букв (единичек). Отбираем массив #2(1) слов с буквами, которых нет в нашем первом слове из массива #1(1).
3. Повторяем операцию до тех пор, пока конечный массив не превратится в слово. Суммируем двоичный код получившейся выборки и проверяем на равенство 11…11 (33 шт).
4. Возвращаемся на массив уровнем выше (предпоследний), берем оттуда второе слово и делаем все то же самое (опускаемся вниз, проверяем на равенство новую выборку). Если слов в нем больше двух, повторяем операцию с третьим и так далее.
5. Продолжаем последовательно подниматься до массива #1(1), где выбираем уже второе слово, вновь опускаемся до конечного «массива» (одно слово), вновь последовательно поднимаемся и опускаемся; возвратившись в массив #1(1), берем третье слово и так далее.
6. Проверив все слова из массива #1(1), возвращаемся в исходную базу, берем 2 слово, получаем массив #1(2) и работаем с ним аналогично.

Перевод в десятичную СС – это просто сокращение записи. Можно назначить буквам «вес», например 1-33 и начать искать слагаемые под сумму 33*(33+1)/2 = 561, но т.к. они разнятся всего на единицу, ложных вариантов будет как минимум 90%. Можно назначить первой букве вес 10^-16, 17-ой – 1, последней – 10^16. В промежутке известно что. Ложные варианты сократятся на порядок. 10 можно заменить и на 100, и на 1000, но я не уверен, будет ли алгоритм подбора слагаемых под сумму корректно обрабатывать такие данные.

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

Еще нашел макросы на расположение букв в слове в алфавитном порядке. Модернизированную таким образом базу можно отсортировать в алфавитном порядке, имеем, таким образом, 33 группы. Далее можно сгруппировать слова по наличию сочетаний АБ – ЮЯ (528), АБВ – ЭЮЯ (5456), АБВГ – ЫЭЯЮ (40920) и уже это использовать как условие для запрета совмещения тех или иных слов.

Если все гораздо проще, то да простит меня Оккам! :)
К сообщению приложен файл: zdfpldf.zip(85.0 Kb)


Сообщение отредактировал magNstr_rYJIon - Пятница, 13.01.2017, 20:17
 
Ответить
СообщениеПРИВЕТСТВИЕ

-Бодрого..
-Не ври, мне, скоту!((

(анаграмма в стиле «тихо сам с собою я веду беседу»)

ВАЖНО

Просматривая профиль тов. Казанского на сайте programmersforum.ru, наткнулся на тему, в комментарии к которой он рекомендует автору (REztor) в случае размещения вопроса на разных форумах, информировать об этом на каждом из них. Отыскав в гугле все форумы, на которых REztor разместил свой вопрос (sql.ru, programmersforum.ru, cyberforum.ru, forum.oszone.net), я таки готов рискнуть и повторить его подвиг. По случаю банкета к вышеупомянутым форумам также присоединяются planetaexcel.ru и excelworld.ru. Ссылки на соответствующие темы:

http://www.sql.ru/forum/1245788/v-poiskah-pangramm-excel-vba
http://programmersforum.ru/showthread.php?t=302720
http://www.cyberforum.ru/vba/thread1899149.html
http://forum.oszone.net/thread-322702.html
http://www.planetaexcel.ru/forum....omoshch

КТО МЫ?

Все мы люди-человеки.

ЧЕГО МЫ ХОТИМ?

На входе имеем базу слов, на выходе – все возможные по условиям панграммы.

УСЛОВИЯ

1. Панграммы ищем для n букв (первостепенно – 33).
2. Все буквы в конечном наборе слов предложении встречаются ровно по 1 разу.
3. Исходная база содержит слова с повторяющимися буквами и/или всякими ненужными символами (какими конкретно – не известно).

МОЙ ВКЛАД

1. Нашел формулу массива для первоначальной сортировки базы:
Код
{=ИЛИ((ДЛСТР(A2)-ДЛСТР(ПОДСТАВИТЬ(СТРОЧН(A2);СИМВОЛ(СТРОКА($1:$255));"")))>1)}

Для слов с повторяющимися буквами выдает ИСТИНА. Далее сортируем, все строки с ИСТИНА в расход, оставляем одни только ЛОЖИ.

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

3. Подумал над алгоритмом для работы с результирующей базой.

ВОЗМОЖНЫЙ АЛГОРИТМ

1. Выводим все буквы слова функцией ПСТР.
2. Создаем двоичный код каждого слова функцией СЧЁТЕСЛИ.
3. Переводим в десятичную систему счисления, поочередно умножая на 2^m (m<33) и затем суммируя. Можно, конечно, объединить все 0 и 1 в громоздкое 33-ёхзначное число, которое потом перегнать функцией ДВВДЕС. Имеем столбец #1 с.. назовем это численной записью числа.
4. Сортируем базу слов по столбцу #1. Имеем численную запись чисел по возрастанию/убыванию.
5. Моя остановочка.

Дело за малым – научиться выделять из столбца #1 диапазон слов с разными буквами, сумма численных значений которых равна (2^33)-1 = 8589934591 (для 33-ёх букв, не говоря уже о количестве вариаций для 32, 31 и т.д.) :)

ЛЁД ТРОНУЛСЯ

Нашел такую весчь, называется подбор слагаемых под нужную сумму. Является частным случаем «задачи о рюкзаке». Наиболее оптимальные на мой беглый взгляд алгоритмы обитают тута (http://www.excelworld.ru/forum/10-5196-1). Вот если бы эту штуку как-то применить в нашей задаче. Описанный мною выше возможный алгоритм можно упростить до записи слов в двоичном коде. Далее:

1. Берем первое слово, сверяем с каждым на наличие одинаковых букв (единичек). Отбираем массив #1(1) слов с буквами, которых нет в нашем первом слове.
2. Берем первое слово из массива #1(1), сверяем с каждым из массива #1(1) на наличие одинаковых букв (единичек). Отбираем массив #2(1) слов с буквами, которых нет в нашем первом слове из массива #1(1).
3. Повторяем операцию до тех пор, пока конечный массив не превратится в слово. Суммируем двоичный код получившейся выборки и проверяем на равенство 11…11 (33 шт).
4. Возвращаемся на массив уровнем выше (предпоследний), берем оттуда второе слово и делаем все то же самое (опускаемся вниз, проверяем на равенство новую выборку). Если слов в нем больше двух, повторяем операцию с третьим и так далее.
5. Продолжаем последовательно подниматься до массива #1(1), где выбираем уже второе слово, вновь опускаемся до конечного «массива» (одно слово), вновь последовательно поднимаемся и опускаемся; возвратившись в массив #1(1), берем третье слово и так далее.
6. Проверив все слова из массива #1(1), возвращаемся в исходную базу, берем 2 слово, получаем массив #1(2) и работаем с ним аналогично.

Перевод в десятичную СС – это просто сокращение записи. Можно назначить буквам «вес», например 1-33 и начать искать слагаемые под сумму 33*(33+1)/2 = 561, но т.к. они разнятся всего на единицу, ложных вариантов будет как минимум 90%. Можно назначить первой букве вес 10^-16, 17-ой – 1, последней – 10^16. В промежутке известно что. Ложные варианты сократятся на порядок. 10 можно заменить и на 100, и на 1000, но я не уверен, будет ли алгоритм подбора слагаемых под сумму корректно обрабатывать такие данные.

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

Еще нашел макросы на расположение букв в слове в алфавитном порядке. Модернизированную таким образом базу можно отсортировать в алфавитном порядке, имеем, таким образом, 33 группы. Далее можно сгруппировать слова по наличию сочетаний АБ – ЮЯ (528), АБВ – ЭЮЯ (5456), АБВГ – ЫЭЯЮ (40920) и уже это использовать как условие для запрета совмещения тех или иных слов.

Если все гораздо проще, то да простит меня Оккам! :)

Автор - magNstr_rYJIon
Дата добавления - 12.01.2017 в 20:51
MCH Дата: Четверг, 12.01.2017, 23:44 | Сообщение № 2
Группа: Админы
Ранг: Старожил
Сообщений: 1906
Репутация: 713 ±
Замечаний: ±

Для начала нужен перечень слов (из книжки или из словаря)
Выложите в виде файла

Далее нужно думать над алгоритмом.
Задача близка к этой: http://www.planetaexcel.ru/forum....D=58223
Но отличается от нее т.к. буквы должны встречаться только по одному разу.

Свести к динамическому программирования не получится, т.к. 2^33 - это слишком большое число, не возможно создать массив такой размерности. (для 26 букв латиницы еще можно попробовать).
Полный перебор скорее всего не возможен (если набор слов будет большим)
Остается жадный алгоритм в какой нибудь вариации.
 
Ответить
СообщениеДля начала нужен перечень слов (из книжки или из словаря)
Выложите в виде файла

Далее нужно думать над алгоритмом.
Задача близка к этой: http://www.planetaexcel.ru/forum....D=58223
Но отличается от нее т.к. буквы должны встречаться только по одному разу.

Свести к динамическому программирования не получится, т.к. 2^33 - это слишком большое число, не возможно создать массив такой размерности. (для 26 букв латиницы еще можно попробовать).
Полный перебор скорее всего не возможен (если набор слов будет большим)
Остается жадный алгоритм в какой нибудь вариации.

Автор - MCH
Дата добавления - 12.01.2017 в 23:44
magNstr_rYJIon Дата: Пятница, 13.01.2017, 17:24 | Сообщение № 3
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
MCH, вот тут имеются всевозможные базы слов. Взял оттуда первые 3 + российские фамилии (зачем не знаю), почистил первой упомянутой в пп формулой, а также сравнил первые 2 базы и удалил дубликаты. Прикрепить удалось почему-то только 2 файла. Гибрид оных добавил в пп. 3-я база и фамилии превышают лимит.

_Boroda_, внимательно ознакомился с каждым пунктом, но нарушений у себя не нашел. Буду очень признателен если вы хотя бы отдаленно намекнете. Название поправил.
К сообщению приложен файл: zdf-win.zip(63.5 Kb) · pldf-win.zip(64.8 Kb)


Сообщение отредактировал magNstr_rYJIon - Пятница, 13.01.2017, 17:29
 
Ответить
СообщениеMCH, вот тут имеются всевозможные базы слов. Взял оттуда первые 3 + российские фамилии (зачем не знаю), почистил первой упомянутой в пп формулой, а также сравнил первые 2 базы и удалил дубликаты. Прикрепить удалось почему-то только 2 файла. Гибрид оных добавил в пп. 3-я база и фамилии превышают лимит.

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

Автор - magNstr_rYJIon
Дата добавления - 13.01.2017 в 17:24
Pelena Дата: Пятница, 13.01.2017, 17:34 | Сообщение № 4
Группа: Админы
Ранг: Местный житель
Сообщений: 14094
Репутация: 3081 ±
Замечаний: ±

Excel 2010, 2016 & Mac Excel
Цитата magNstr_rYJIon, 13.01.2017 в 17:24, в сообщении № 4 ()
отдаленно намекнете

Формулу следует оформлять тегами (кнопка fx)


"Черт возьми, Холмс! Но как??!!"
ЯД 41001765434816
 
Ответить
Сообщение
Цитата magNstr_rYJIon, 13.01.2017 в 17:24, в сообщении № 4 ()
отдаленно намекнете

Формулу следует оформлять тегами (кнопка fx)

Автор - Pelena
Дата добавления - 13.01.2017 в 17:34
Manyasha Дата: Пятница, 13.01.2017, 17:44 | Сообщение № 5
Группа: Модераторы
Ранг: Старожил
Сообщений: 2198
Репутация: 893 ±
Замечаний: 0% ±

Excel 2010, 2016
magNstr_rYJIon, к замечанию о формулах: Вы привели ссылки на форумы, где Вы опубликовали эту же тему? Если да, дайте ссылки на саму тему на форумах, а не на главные страницы.


ЯД: 410013299366744 WM: R193491431804
 
Ответить
СообщениеmagNstr_rYJIon, к замечанию о формулах: Вы привели ссылки на форумы, где Вы опубликовали эту же тему? Если да, дайте ссылки на саму тему на форумах, а не на главные страницы.

Автор - Manyasha
Дата добавления - 13.01.2017 в 17:44
MCH Дата: Пятница, 13.01.2017, 17:57 | Сообщение № 6
Группа: Админы
Ранг: Старожил
Сообщений: 1906
Репутация: 713 ±
Замечаний: ±

К задаче можно применить линейное программирование, в качестве решателя использовал OpenSolver

При использовании слов из словаря нашлось несколько решений:

Еще вариант, некоторые буквы повторяются, но всего 5 слов:
брызжущий вгорячах фетюк съёмцы эндшпиль
 
Ответить
СообщениеК задаче можно применить линейное программирование, в качестве решателя использовал OpenSolver

При использовании слов из словаря нашлось несколько решений:

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

Автор - MCH
Дата добавления - 13.01.2017 в 17:57
magNstr_rYJIon Дата: Пятница, 13.01.2017, 20:41 | Сообщение № 7
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Pelena, оформил, спасибо! :)

Manyasha, разместил ссылки (по возможности на остальных форумах тоже), спасибо! :)

MCH, чуточку подробнее можно о том, как все это работает? Чтобы у меня была возможность повторить аналогичные вычисления на уже значительно более больших базах слов, включающих словоформы.
 
Ответить
СообщениеPelena, оформил, спасибо! :)

Manyasha, разместил ссылки (по возможности на остальных форумах тоже), спасибо! :)

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

Автор - magNstr_rYJIon
Дата добавления - 13.01.2017 в 20:41
MCH Дата: Суббота, 14.01.2017, 09:33 | Сообщение № 8
Группа: Админы
Ранг: Старожил
Сообщений: 1906
Репутация: 713 ±
Замечаний: ±

Цитата magNstr_rYJIon, 13.01.2017 в 20:41, в сообщении № 8 ()
чуточку подробнее можно о том, как все это работает?

1. берем словарь или текст, удаляем из него дубликаты, слова содержащие повторяющиеся буквы, слова состоящие из 1-2 букв. (у меня по первому словарю получилось более 24 тыс. слов)
2. составляем двухмерную матрицу слова/буквы (24Кх33), где по вертикали слова, по горизонтали буквы и признак 1/0 нахождения буквы в слове.
3. Составляем линейную модель для решения ее симплекс-методом,
целевая функция - наименьшее количество слов (или заданное количество слов),
ограничение - каждое слово может входить в фразу или не входить (бинарное 1/0), каждая буква должна быть использована по одному разу.
Задача не для MS Solver, т.к. в нем только 200 изменяемых ячеек, а вот OpenSolver или LPSolve справляются с данной задачей

Различные варианты фраз можно получить изменяя сортировку исходных слов и/или устанавливая различные ограничения и целевую функцию

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

Файл с реализованной моделью можно скачать здесь: https://yadi.sk/d/xyNhLJFk38tktB
 
Ответить
Сообщение
Цитата magNstr_rYJIon, 13.01.2017 в 20:41, в сообщении № 8 ()
чуточку подробнее можно о том, как все это работает?

1. берем словарь или текст, удаляем из него дубликаты, слова содержащие повторяющиеся буквы, слова состоящие из 1-2 букв. (у меня по первому словарю получилось более 24 тыс. слов)
2. составляем двухмерную матрицу слова/буквы (24Кх33), где по вертикали слова, по горизонтали буквы и признак 1/0 нахождения буквы в слове.
3. Составляем линейную модель для решения ее симплекс-методом,
целевая функция - наименьшее количество слов (или заданное количество слов),
ограничение - каждое слово может входить в фразу или не входить (бинарное 1/0), каждая буква должна быть использована по одному разу.
Задача не для MS Solver, т.к. в нем только 200 изменяемых ячеек, а вот OpenSolver или LPSolve справляются с данной задачей

Различные варианты фраз можно получить изменяя сортировку исходных слов и/или устанавливая различные ограничения и целевую функцию

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

Файл с реализованной моделью можно скачать здесь: https://yadi.sk/d/xyNhLJFk38tktB

Автор - MCH
Дата добавления - 14.01.2017 в 09:33
Мир MS Excel » Вопросы и решения » Вопросы по VBA » Поиск панграмм из произвольной базы слов в Excel макросом (Макросы/Sub)
  • Страница 1 из 1
  • 1
Поиск:

Яндекс цитирования
© 2010-2019 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!