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

Программирование - Практика программирования

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

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

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

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

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

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

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

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

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

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

См. также

Комментарии
1. Марат Настоящий (rayastar) 60 12.12.13 15:16 Сейчас в теме
По необходимости могу выложить работу на управляемых формах
2. Ярослав Радкевич (WKBAPKA) 201 12.12.13 16:51 Сейчас в теме
а есть что нибудь для необычных приложений?
3. Марат Настоящий (rayastar) 60 12.12.13 17:47 Сейчас в теме
(2) WKBAPKA, есть "что нибудь" для управляемого приложения)
4. Миклухо Маклай (mikuho) 89 12.12.13 22:21 Сейчас в теме
Долго переделывали алгоритм?
5. Марат Настоящий (rayastar) 60 13.12.13 08:31 Сейчас в теме
(4) mikuho, алгоритм переделывал с паскаля. но собирал его из двух исходников. в целом, ушло около 6 часов на написание(pascal) и перенос на 1С. Много возникало нюансов по поводу генерации случайных чисел. Не обошлось без помощи коллег)
6. Андрей Акулов (DrAku1a) 1201 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) 60 18.12.13 08:37 Сейчас в теме
(6) DrAku1a, Согласен, есть простое понимание. А есть универсальное, в котором не нужно учитывать количество циклом и писать 20 "Для Каждого Цикл". Главное свойство любого алгоритма - оптимальность и универсальность.
8. Александр Медведев (anig99) 2525 28.12.13 09:20 Сейчас в теме
не совсем понимаю зачем это, но плюс
9. Марат Настоящий (rayastar) 60 28.12.13 13:21 Сейчас в теме
(8) anig99, В прикладных задачах найти применение трудно. Я писал конфигурацию по Лото(сбор, анализ данных, планирование ставок и тому подобное) Если интересно - могу выложить на всеобщее обозрение. Вот как раз там я использовал данный алгоритм
10. Миклухо Маклай (mikuho) 89 01.01.14 19:42 Сейчас в теме
(9) rayastar, а что за конфигурация, можно по подробней? я кажется пишу нечто подобное
11. Марат Настоящий (rayastar) 60 01.01.14 20:43 Сейчас в теме
(10) mikuho, анализ данных лото. делал летом этого года, около 5-6 месяцев)
12. Марат Настоящий (rayastar) 60 01.01.14 20:43 Сейчас в теме
Могу выложить на всеобщее обозрение
Оставьте свое сообщение