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

Вход

Регистрация

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

 

= Мир MS Excel/Комбинаторика: сочетания, перестановки, размещения - Мир MS Excel

Старая форма входа
  • Страница 1 из 1
  • 1
Модератор форума: _Boroda_, китин  
Комбинаторика: сочетания, перестановки, размещения
MCH Дата: Пятница, 08.12.2017, 08:53 | Сообщение № 1
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Начало здесь: http://www.excelworld.ru/forum/3-12712-1

Во вложении генераторы сочетаний, перестановок и размещений без повторений.
Реализовано в виде отдельных функций, которые генерируют последующие расстановки чисел в массиве.
Не используются рекурсии, не требуются глобальные массивы или переменные.

Думаю, что будет удобно использовать для решения задач, требующих перебора комбинаций.
К сообщению приложен файл: Combin.xlsm (29.5 Kb)
 
Ответить
СообщениеНачало здесь: http://www.excelworld.ru/forum/3-12712-1

Во вложении генераторы сочетаний, перестановок и размещений без повторений.
Реализовано в виде отдельных функций, которые генерируют последующие расстановки чисел в массиве.
Не используются рекурсии, не требуются глобальные массивы или переменные.

Думаю, что будет удобно использовать для решения задач, требующих перебора комбинаций.

Автор - MCH
Дата добавления - 08.12.2017 в 08:53
Кайли Дата: Суббота, 13.01.2018, 23:51 | Сообщение № 2
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 118
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Любимая тема)


Привет Мир!
 
Ответить
СообщениеЛюбимая тема)

Автор - Кайли
Дата добавления - 13.01.2018 в 23:51
gluchonemoi Дата: Воскресенье, 23.01.2022, 15:51 | Сообщение № 3
Группа: Пользователи
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 0% ±

MCH, день добрый!
В приведённом вами примере есть хороший макрос расчёта сочетаний, но в котором количество сочетаний ограничено количеством строк на листе.
Разумеется в интернете есть варианты с выводом всех возможных сочетаний на одном или на нескольких листах (у меня сочетания для варианта "5 из 70 " выводятся на 12 листах). Если сам расчёт занимает не так много времени, то дальнейшая работа с такими огромными массивами (например, фильтрация с удалением строк с ненужными сочетаниями) требует много памяти от компьютера, времени и часто приводит к зависанию Excel.

Можно ли создать макрос, в котором сочетания генерируются с учётом нескольких условий?
например:
- по заданному диапазону сумм чисел, входящих в сочетание;
- по заданному диапазону дисперсии чисел, входящих в сочетание;
- по заданному количеству чётных чисел;
- по заданному количеству чисел, не превышающих какого-то значения...


Сообщение отредактировал gluchonemoi - Воскресенье, 23.01.2022, 19:13
 
Ответить
СообщениеMCH, день добрый!
В приведённом вами примере есть хороший макрос расчёта сочетаний, но в котором количество сочетаний ограничено количеством строк на листе.
Разумеется в интернете есть варианты с выводом всех возможных сочетаний на одном или на нескольких листах (у меня сочетания для варианта "5 из 70 " выводятся на 12 листах). Если сам расчёт занимает не так много времени, то дальнейшая работа с такими огромными массивами (например, фильтрация с удалением строк с ненужными сочетаниями) требует много памяти от компьютера, времени и часто приводит к зависанию Excel.

Можно ли создать макрос, в котором сочетания генерируются с учётом нескольких условий?
например:
- по заданному диапазону сумм чисел, входящих в сочетание;
- по заданному диапазону дисперсии чисел, входящих в сочетание;
- по заданному количеству чётных чисел;
- по заданному количеству чисел, не превышающих какого-то значения...

Автор - gluchonemoi
Дата добавления - 23.01.2022 в 15:51
MCH Дата: Воскресенье, 23.01.2022, 21:36 | Сообщение № 4
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

В данном варианте - это просто алгоритмы, которые позволяют генерировать следующую расстановку чисел из текущей (следующее сочетание, следующее размещение или следующую перестановку)
Генерировать все варианты и выводить их на лист не обязательно, фильтровать данные можно в процессе генерации
меня сочетания для варианта "5 из 70 " выводятся на 12 листах). Если сам расчёт занимает не так много времени, то дальнейшая работа с такими огромными массивами (например, фильтрация с удалением строк с ненужными сочетаниями) требует много памяти от компьютера, времени и часто приводит к зависанию Excel

У Вас как раз пример, когда не нужно генерировать все сочетания и выводить их на лист, можно фильтровать данные в процессе генерации
(ЧИСЛКОМБ(70;5) = 12103014, генерация 12 миллионов комбинаций - пара секунд, можно сразу макросом с ними производить вычисления)

Для ускорения переборов можно использовать метод ветвей и границ (МВиГ), отсекая не перспективные ветви решения, что позволяет значительно сократить расчеты
Если знать Вашу задачу, то, наверное, можно предложить и другие алгоритмы для ее решения
 
Ответить
СообщениеВ данном варианте - это просто алгоритмы, которые позволяют генерировать следующую расстановку чисел из текущей (следующее сочетание, следующее размещение или следующую перестановку)
Генерировать все варианты и выводить их на лист не обязательно, фильтровать данные можно в процессе генерации
меня сочетания для варианта "5 из 70 " выводятся на 12 листах). Если сам расчёт занимает не так много времени, то дальнейшая работа с такими огромными массивами (например, фильтрация с удалением строк с ненужными сочетаниями) требует много памяти от компьютера, времени и часто приводит к зависанию Excel

У Вас как раз пример, когда не нужно генерировать все сочетания и выводить их на лист, можно фильтровать данные в процессе генерации
(ЧИСЛКОМБ(70;5) = 12103014, генерация 12 миллионов комбинаций - пара секунд, можно сразу макросом с ними производить вычисления)

Для ускорения переборов можно использовать метод ветвей и границ (МВиГ), отсекая не перспективные ветви решения, что позволяет значительно сократить расчеты
Если знать Вашу задачу, то, наверное, можно предложить и другие алгоритмы для ее решения

Автор - MCH
Дата добавления - 23.01.2022 в 21:36
gluchonemoi Дата: Воскресенье, 23.01.2022, 23:37 | Сообщение № 5
Группа: Пользователи
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 0% ±

MCH, так и я о том же: нужен макрос, который фильтрует сочетания именно в процессе их генерации


Сообщение отредактировал gluchonemoi - Воскресенье, 23.01.2022, 23:47
 
Ответить
СообщениеMCH, так и я о том же: нужен макрос, который фильтрует сочетания именно в процессе их генерации

Автор - gluchonemoi
Дата добавления - 23.01.2022 в 23:37
gluchonemoi Дата: Воскресенье, 23.01.2022, 23:40 | Сообщение № 6
Группа: Пользователи
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 0% ±

У Вас как раз пример, когда не нужно генерировать все сочетания и выводить их на лист, можно фильтровать данные в процессе генерации
(ЧИСЛКОМБ(70;5) = 12103014, генерация 12 миллионов комбинаций - пара секунд, можно сразу макросом с ними производить вычисления)
MCH, так и я о том же: нужен макрос, который фильтрует сочетания именно в процессе их генерации

Задача: имеется числовая лотерея, в которой надо угадать 5 из 70 чисел.

Число возможных сочетаний более 12 млн. Чтобы уменьшить их количество отбрасываем числа из последних 2-3 тиражей, из оставшихся чисел формируем массив (допустим, в столбце А).
В параметрах фильтров устанавливаем граничные условия (минимальное и максимальное значение полосы прорускания)
Запускаем макрос, который генерирует сочетания, удовлетворяющие условиям фильтров.

Фильтры основаны на анализе всех теоретически возможных сочетаний и результатов уже прошедших тиражей. Ширина полосы пропускания выбирается пользователем: для "жёсткого" фильтра это 2 стандартных отклонения от значения моды (остаётся ~ 65% всех возможных сочетаний), для "мягкого" - 4 стандартных отклонения (95%), возможен и произвольный диапазон.

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

Нечто подобное вами было реализовано в 2013 году (макрос LimitBtuteForce), который выполняет подбор чисел под заданную сумму. При использовании этого макроса и ~ 40 фильтров время обработки массива для лотереи "5 из 36" составляет не более 2 минут, при этом число сочетаний сокращается до полутора десятков.
 
Ответить
Сообщение
У Вас как раз пример, когда не нужно генерировать все сочетания и выводить их на лист, можно фильтровать данные в процессе генерации
(ЧИСЛКОМБ(70;5) = 12103014, генерация 12 миллионов комбинаций - пара секунд, можно сразу макросом с ними производить вычисления)
MCH, так и я о том же: нужен макрос, который фильтрует сочетания именно в процессе их генерации

Задача: имеется числовая лотерея, в которой надо угадать 5 из 70 чисел.

Число возможных сочетаний более 12 млн. Чтобы уменьшить их количество отбрасываем числа из последних 2-3 тиражей, из оставшихся чисел формируем массив (допустим, в столбце А).
В параметрах фильтров устанавливаем граничные условия (минимальное и максимальное значение полосы прорускания)
Запускаем макрос, который генерирует сочетания, удовлетворяющие условиям фильтров.

Фильтры основаны на анализе всех теоретически возможных сочетаний и результатов уже прошедших тиражей. Ширина полосы пропускания выбирается пользователем: для "жёсткого" фильтра это 2 стандартных отклонения от значения моды (остаётся ~ 65% всех возможных сочетаний), для "мягкого" - 4 стандартных отклонения (95%), возможен и произвольный диапазон.

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

Нечто подобное вами было реализовано в 2013 году (макрос LimitBtuteForce), который выполняет подбор чисел под заданную сумму. При использовании этого макроса и ~ 40 фильтров время обработки массива для лотереи "5 из 36" составляет не более 2 минут, при этом число сочетаний сокращается до полутора десятков.

Автор - gluchonemoi
Дата добавления - 23.01.2022 в 23:40
  • Страница 1 из 1
  • 1
Поиск:

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