gifts2017

Генерация сочетаний (Обычное приложение)

Опубликовал Марат Настоящий (rayastar) в раздел Программирование - Практика программирования

Генератор сочетаний 1С

Сочетаниями из n элементов по k называются соединения, которые можно образовать из n элементов, собирая в каждое соединение k элементов; при этом соединения отличаются друг от друга только самими элементами (различие порядка их расположения во внимание не принимается).

Например, из 3 элементов (a,b,c) по 2 можно образовать следующие сочетания: ab, ac, bc.

Число всех возможных сочетаний, которые можно образовать из n элементов по k, обозначается символом Cnk и вычисляется по формуле:

За основу математических алгоритмов был взяты статьи с http://algolist.manual.ru/maths/combinat/

Так же хочется поблагодарить пользователя noblekey за его алгоритм генерации случайных чисел. Код был взят с публикации http://infostart.ru/public/57305/

Алгоритм генерации сочетаний обширно использовался мною на олимпиадах по 1С.

Возможно, есть более быстрые решения. Обработка поддерживает максимально число из 20 цифр, но можно добавить в табличную часть "Числа" реквизиты вида "Цифра_21","Цифра_22" и больше, и после чего будет поддерживаться числа, длиной больше 20 цифр.

Скачать файлы

Наименование Файл Версия Размер
Сочетания 14
.epf 12,80Kb
11.12.13
14
.epf 12,80Kb Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Марат Настоящий (rayastar) 12.12.13 15:16
По необходимости могу выложить работу на управляемых формах
2. Ярослав Радкевич (WKBAPKA) 12.12.13 16:51
а есть что нибудь для необычных приложений?
3. Марат Настоящий (rayastar) 12.12.13 17:47
(2) WKBAPKA, есть "что нибудь" для управляемого приложения)
4. Миклухо Маклай (mikuho) 12.12.13 22:21
Долго переделывали алгоритм?
5. Марат Настоящий (rayastar) 13.12.13 08:31
(4) mikuho, алгоритм переделывал с паскаля. но собирал его из двух исходников. в целом, ушло около 6 часов на написание(pascal) и перенос на 1С. Много возникало нюансов по поводу генерации случайных чисел. Не обошлось без помощи коллег)
6. Андрей Акулов (DrAku1a) 18.12.13 07:03
Алгоритм?
В самом простом для понимания виде:
F = N-k+1;
Для сч1=1 По F Цикл
	Для сч2 = сч1+1 По F+1 Цикл
		Для сч3 = сч2+1 По F+2 Цикл
		...
                // и таких циклов k штук
		
                Комбинация = (сч1, сч2, сч3, ..., счk);

		...
		КонецЦикла;
	КонецЦикла;
КонецЦикла;
...Показать Скрыть
Вот из жизни: подходишь к двери, на ней кодовый замок (нужно нажать три кнопки из десяти и дверка откроется, визуально код определить не возможно - на кнопках нет потёртостей). Нужно перебрать все возможные варианты.
Алгоритм перебора:
1. Зажимаешь пальцами одной руки 1 и 2, перебираешь свободной клавиши 3,4,5,6,7,8,9,0,
2. Далее зажимаешь 1 и 3, перебираешь 4,5,6,7,8,9,0 (2 не надо, т.к. 123 равнозначно 132)
... и так до 1 и 8, нажимаешь 9.
3. Зажимаешь 2 и 3, перебираешь 4,5,6,7,8,9,0 (1 не надо, т.к. с ним уже все комбинации перебрали)
4. Зажимаешь 2 и 4, перебираешь 5,6,7,8,9,0
и так до 8-9-0
или тоже самое в коде:
Для сч1=1 По 8 Цикл
	Для сч2 = сч1+1 По 9 Цикл
		Для сч3 = сч2+1 По 10 Цикл
			ПроверитьКомбинацию(сч1, сч2, ?(сч3=10, 0, сч3));
		КонецЦикла;
	КонецЦикла;
КонецЦикла;
...Показать Скрыть
Для общего случая, когда N и k заранее неизвестны - подойдет использование рекурсии.
7. Марат Настоящий (rayastar) 18.12.13 08:37
(6) DrAku1a, Согласен, есть простое понимание. А есть универсальное, в котором не нужно учитывать количество циклом и писать 20 "Для Каждого Цикл". Главное свойство любого алгоритма - оптимальность и универсальность.
8. Александр Медведев (anig99) 28.12.13 09:20
не совсем понимаю зачем это, но плюс
9. Марат Настоящий (rayastar) 28.12.13 13:21
(8) anig99, В прикладных задачах найти применение трудно. Я писал конфигурацию по Лото(сбор, анализ данных, планирование ставок и тому подобное) Если интересно - могу выложить на всеобщее обозрение. Вот как раз там я использовал данный алгоритм
10. Миклухо Маклай (mikuho) 01.01.14 19:42
(9) rayastar, а что за конфигурация, можно по подробней? я кажется пишу нечто подобное
11. Марат Настоящий (rayastar) 01.01.14 20:43
(10) mikuho, анализ данных лото. делал летом этого года, около 5-6 месяцев)
12. Марат Настоящий (rayastar) 01.01.14 20:43
Могу выложить на всеобщее обозрение
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа