Всем привет! Кодить не умею, но есть идея одного интересного алгоритма. Сначала думал, что можно обойтись только формулами и старыми добрыми руками, но уже после первых промежуточных результатов в очередной раз убедился в своей наивности.
Вдохновение я черпал из приставок (русского языка). Комбинируя любую из них с разными корнями, каждый раз получаем новое по значению (относительно исходного корня) слово. Да и между собой эти слова отличаются, несмотря на характеристику общей приставки.
А почему бы нам не взять да и поделить все слова на две части и составить некий рейтинг их сочетаний? Навскидку:
Для привлекательности нашего «исследования» слова в конечной таблице можно заменить картинками (что я и сделал, ищите ниже ссылку на файл).
Что cделал я:
1. Отсортировал базу слов по длине, вырезал все выше 8. 2. Отрезал поочередно от 1 до 7 букв с начала слова (7 столбцов). Потом то же самое, только с конца (еще 7 столбцов). 3. Скопировал получившиеся 14 столбцов рядом, макросом удалил дубликаты в каждом отдельном столбце. 4. Сравнил попарно каждые 14N+1 столбцов, подсчитал количество вариаций обрезанных частей (еще 14 столбцов). 5. Скопировал попарно рядом каждые14(N+1)+2M+1 столбцов. Из-за увеличенного шага далее пришлось повторять операцию, но уже для каждых 14(N+1)+2M ячеек. В результате получился выход 1A, 3A, 5A, 7A, 2B, 4B, 6B и далее то же, только вместо A – B, а вместо B – A. Здесь 1-7(A) – кусок, отрезанный с начала, а 1-7(B) – с конца каждого слова. 6. Отсортировал каждую пару по второму столбцу по убыванию. Результатом можно полюбоваться вот тут.
Далее я думал упорядочить 1-7(A) в один столбец A, а 1-7(B) – в одну строку B и сделать таблицу. Но беглое сравнение результатов меня быстро отрезвило. Погуглил на эту тематику, нашел вот такую замечательную статью из которой узнал про метод N-грамм.
Что нужно сделать:
1. Автоматическая сортировка базы по длине и удаление всех слов с длиной менее N и более M. 2. Начинаем отрезать куски с начала слова макросом без вывода. Минимальную длину обрезки K и максимальную L предварительно можно задать. 3. К каждому куску с начала (A) привязана группа кусков с конца (группа B). Сортируем их по размеру группы B. 4. Выбираем группу со средним значением (или одну из них, если несколько равных) и проверяем ее на 100% сходство по набору B поочередно с каждой группой, у которой значение выше.
Наша задача на данном этапе – выделить среди всех групп такой набор B, чтобы произведение кол.-ва B в наборе на кол.-во групп, в которых этот набор 100% присутствует, было максимальным.
На примере: у нас 1500 слов, 10000 A, соот.-но 10000 групп B. Минимальное кол.-во B в группе – 1, максимальное – 300. В качестве набора выбираем «группу» из 1 B. Допустим это B распространенное, и оно есть в 150 группах. 1*150=150. Потом берем в качестве набора максимальную по количеству B группу. Групп с таким набором, скажем, одна. 300*1=300. Короче суть:
Очень удачно совпало (после ряда подгонов) кол.-во B в наборе (300/2) с максимальным произведением. Весь пример можно посмотреть на 2-м листе. Формулу (циклически возрастающей арифметической прогрессии) – на 3-м.
И это только по одному конкретному набору на каждое количество! Перебирать мы их все конечно не будем, только средние ±X, для автоматической проверки.
Но тут еще встает вопрос – а не окажется ли так, что максимальное произведение будет у набора, которого вообще нет ни у одного A? Кол.-во B там будет как раз 150±X, а вот каких именно из 300 – загадка. Здесь можно дополнительно задействовать процентное сравнение групп:
А) Берем 1-ю группу, сравниваем со 2-ой, запоминаем % совпадений относительно каждой группы, затем сравниваем с 3-ей и т.д. Б) Все то же самое, только 2-ую группу мы уже не сравниваем с первой. В) И так далее, до предпоследней, которую сравниваем только с последней, итого делаем почти в 2 раза меньше операций. Г) Складываем % относительно каждой отдельной группы, умножаем на количество B в группе, максимальный результат – группа с желанным набором.
Вообще процентное сравнение интересная идея, но вот то, что я описал – не факт. Едем дальше.
5) Нашли-таки мы этот набор. Удаляем его из всех групп, в которые он входит на 100% (запоминаем все группы, точнее A, которым они соответствуют в порядке убывания по количеству B в группе), получаем новый массив групп, для которого ищем новый набор. 6) Продолжаем до тех пор, пока не останутся группы с одним элементом B. 7) Выводим столбиком, начиная с ячейки A2 все полученные A – от первого набора, от второго и т.д. 8) Возвращаемся к п.2, но вместо A отрезаем B. Повторяем для них п.3 – п.6. 9) Выводим в строчку, начиная с ячейки B1 все полученные A – от первого набора, от второго и т.д. 10) Если это возможно, суммируем текст в ячейках, но по условию – строго на определенных площадях:
На тему убил как минимум 3 часа чистого времени, т.е. на текст, примеры и картинки. Вот такая я черепаха. До сих пор не уверен будет ли оно работать и что еще добавить чтобы уж наверняка. Пишите критику, тыкайте носом в ошибки; пишите пожелания, дополнения, идеи; пишите все то же самое, но так, чтобы это стало понятно и доступно мне и всем остальным. Главное – пишите!
Всем привет! Кодить не умею, но есть идея одного интересного алгоритма. Сначала думал, что можно обойтись только формулами и старыми добрыми руками, но уже после первых промежуточных результатов в очередной раз убедился в своей наивности.
Вдохновение я черпал из приставок (русского языка). Комбинируя любую из них с разными корнями, каждый раз получаем новое по значению (относительно исходного корня) слово. Да и между собой эти слова отличаются, несмотря на характеристику общей приставки.
А почему бы нам не взять да и поделить все слова на две части и составить некий рейтинг их сочетаний? Навскидку:
Для привлекательности нашего «исследования» слова в конечной таблице можно заменить картинками (что я и сделал, ищите ниже ссылку на файл).
Что cделал я:
1. Отсортировал базу слов по длине, вырезал все выше 8. 2. Отрезал поочередно от 1 до 7 букв с начала слова (7 столбцов). Потом то же самое, только с конца (еще 7 столбцов). 3. Скопировал получившиеся 14 столбцов рядом, макросом удалил дубликаты в каждом отдельном столбце. 4. Сравнил попарно каждые 14N+1 столбцов, подсчитал количество вариаций обрезанных частей (еще 14 столбцов). 5. Скопировал попарно рядом каждые14(N+1)+2M+1 столбцов. Из-за увеличенного шага далее пришлось повторять операцию, но уже для каждых 14(N+1)+2M ячеек. В результате получился выход 1A, 3A, 5A, 7A, 2B, 4B, 6B и далее то же, только вместо A – B, а вместо B – A. Здесь 1-7(A) – кусок, отрезанный с начала, а 1-7(B) – с конца каждого слова. 6. Отсортировал каждую пару по второму столбцу по убыванию. Результатом можно полюбоваться вот тут.
Далее я думал упорядочить 1-7(A) в один столбец A, а 1-7(B) – в одну строку B и сделать таблицу. Но беглое сравнение результатов меня быстро отрезвило. Погуглил на эту тематику, нашел вот такую замечательную статью из которой узнал про метод N-грамм.
Что нужно сделать:
1. Автоматическая сортировка базы по длине и удаление всех слов с длиной менее N и более M. 2. Начинаем отрезать куски с начала слова макросом без вывода. Минимальную длину обрезки K и максимальную L предварительно можно задать. 3. К каждому куску с начала (A) привязана группа кусков с конца (группа B). Сортируем их по размеру группы B. 4. Выбираем группу со средним значением (или одну из них, если несколько равных) и проверяем ее на 100% сходство по набору B поочередно с каждой группой, у которой значение выше.
Наша задача на данном этапе – выделить среди всех групп такой набор B, чтобы произведение кол.-ва B в наборе на кол.-во групп, в которых этот набор 100% присутствует, было максимальным.
На примере: у нас 1500 слов, 10000 A, соот.-но 10000 групп B. Минимальное кол.-во B в группе – 1, максимальное – 300. В качестве набора выбираем «группу» из 1 B. Допустим это B распространенное, и оно есть в 150 группах. 1*150=150. Потом берем в качестве набора максимальную по количеству B группу. Групп с таким набором, скажем, одна. 300*1=300. Короче суть:
Очень удачно совпало (после ряда подгонов) кол.-во B в наборе (300/2) с максимальным произведением. Весь пример можно посмотреть на 2-м листе. Формулу (циклически возрастающей арифметической прогрессии) – на 3-м.
И это только по одному конкретному набору на каждое количество! Перебирать мы их все конечно не будем, только средние ±X, для автоматической проверки.
Но тут еще встает вопрос – а не окажется ли так, что максимальное произведение будет у набора, которого вообще нет ни у одного A? Кол.-во B там будет как раз 150±X, а вот каких именно из 300 – загадка. Здесь можно дополнительно задействовать процентное сравнение групп:
А) Берем 1-ю группу, сравниваем со 2-ой, запоминаем % совпадений относительно каждой группы, затем сравниваем с 3-ей и т.д. Б) Все то же самое, только 2-ую группу мы уже не сравниваем с первой. В) И так далее, до предпоследней, которую сравниваем только с последней, итого делаем почти в 2 раза меньше операций. Г) Складываем % относительно каждой отдельной группы, умножаем на количество B в группе, максимальный результат – группа с желанным набором.
Вообще процентное сравнение интересная идея, но вот то, что я описал – не факт. Едем дальше.
5) Нашли-таки мы этот набор. Удаляем его из всех групп, в которые он входит на 100% (запоминаем все группы, точнее A, которым они соответствуют в порядке убывания по количеству B в группе), получаем новый массив групп, для которого ищем новый набор. 6) Продолжаем до тех пор, пока не останутся группы с одним элементом B. 7) Выводим столбиком, начиная с ячейки A2 все полученные A – от первого набора, от второго и т.д. 8) Возвращаемся к п.2, но вместо A отрезаем B. Повторяем для них п.3 – п.6. 9) Выводим в строчку, начиная с ячейки B1 все полученные A – от первого набора, от второго и т.д. 10) Если это возможно, суммируем текст в ячейках, но по условию – строго на определенных площадях:
На тему убил как минимум 3 часа чистого времени, т.е. на текст, примеры и картинки. Вот такая я черепаха. До сих пор не уверен будет ли оно работать и что еще добавить чтобы уж наверняка. Пишите критику, тыкайте носом в ошибки; пишите пожелания, дополнения, идеи; пишите все то же самое, но так, чтобы это стало понятно и доступно мне и всем остальным. Главное – пишите!