gifts2017

Функция для получения возможных перестановок или комбинаторика для 1С-нега

Опубликовал Andrey Smirnov (dusha0020) в раздел Программирование - Практика программирования

Функция, возвращающая массив всех возможных перестановок произвольного множества, состоящих из заданного количества элементов. С повторениями элементов или без.

Понадобилось (не спрашивайте зачем) найти и проанализировать все возможные комбинации элементов массива произвольной длины. Задача хрестоматийная. Так как число возможных элементов и длина комбинации на этапе постановки задачи не определены, напрашивается рекурсивное решение. И что же я нахожу по теме? Ничего для 1С, но множество всяких разных реализаций на Сях, Дельфях и даже VBA.

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

Погордился собой минут 20 и решил поделиться с сообществом. Может, кому-нибудь пригодится, и будет моей карме лишний лайк:)

Сама функция:

//мЭлементов 		- массив произвольных элементов, образующих комбинации. Произвольный.
//ДлинаПерестановки	- количество элементов в комбинации. Целое.
//БезПовторов		- признак необходимости получать в результате комбинации в которых один и тот же элемент мЭлементов встречался бы не чаще 1 раза. Булево. По умолчанию - Ложь.

Функция Перестановки(мЭлементов, ДлинаПерестановки, БезПовторов = Ложь, Основание = Неопределено, мРезультата = Неопределено, ТекУровень = 0) Экспорт
	
	Если Основание = Неопределено Тогда Основание = Новый Массив КонецЕсли;
	Если мРезультата = Неопределено Тогда мРезультата = Новый Массив КонецЕсли;
	
	Если ТекУровень < ДлинаПерестановки - 1 Тогда		
		Для Каждого Элемент Из мЭлементов Цикл	
			Если БезПовторов И НЕ Основание.Найти(Элемент) = Неопределено Тогда
			Иначе
				Основание.Добавить(Элемент);
				мРезультата = Перестановки(мЭлементов, ДлинаПерестановки, БезПовторов, Основание, мРезультата, ТекУровень + 1);
				Основание.Удалить(Основание.Количество() - 1);
			КонецЕсли;
		КонецЦикла;
	Иначе
		Для Каждого Элемент Из мЭлементов Цикл
			Если БезПовторов И НЕ Основание.Найти(Элемент) = Неопределено Тогда
			Иначе
				Основание.Добавить(Элемент);
				мРезультата.Добавить(Новый ФиксированныйМассив(Основание));
				Основание.Удалить(Основание.Количество()-1);
			КонецЕсли;
		КонецЦикла;	
	КонецЕсли;	
	Возврат мРезультата;	
КонецФункции

По аргументам все, надеюсь, понятно из описания. По результатам: на выходе получаем массив из фиксированных массивов. Фиксированный массив - возможная комбинация, а количество элементов результирующего массива и есть количество найденных (возможных) комбинаций. Каждый фиксированный массив состоит из ДлинаПерестановки элементов массива мЭлементов - то есть какой-то набор элементов первоначального множества значений. Или одна из возможных комбинаций.

Очевидная вещь, но все таки предупрежу. Если ДлинаПерестановки в аргументах будет больше числа элементов в массиве мЭлементов, а условие уникальности при этом будет Истина, в результате Вы получите замечательный, но пустой массив результатов. Почему? Да потому, что нельзя собрать из Х возможных  элементов комбинацию длиной в Y, не повторяясь, если X<Y. Допустим, в 11 разрядном десятичном числе как минимум одна из цифр должна повториться дважды. Вот как-то так получается:)

Всё!

P.S. Предвидя возмущения широкой общественности по поводу "нафига нам честным, умным, скромным и обычным 1С-негам это нужно" вспомнил одну  публикацию по теме, как помочь бухгалтеру найти, какие же из возможных чисел образуют в сумме ошибку. Вот Вам и готовая сфера применения функции. И при этом используется настоящий, выдержанный и марочный 1С, а не Java:)

См. также

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

Комментарии

1. Андрей Назаров (Zeskord) 08.06.15 12:57
Посмотрите в БСП функцию
УправлениеДоступомСлужебный.ВсеКомбинацииВидовДоступа

Там эта задача по-другому решена.
2. Andrey Smirnov (dusha0020) 08.06.15 15:28
(1) Zeskord, К сожалению у меня в БСП такой функции нет.
3. Марат Настоящий (rayastar) 08.06.15 19:19
4. Владимир (vova-1c) 08.06.15 22:07
На мой взгляд очень даже хорошо.
5. Andrey Smirnov (dusha0020) 09.06.15 08:26
(3) rayastar, А почему слегка? Не качал Вашу работу, но подозреваю что суть алгоритма генерации комбинаций все та же - рекурсивный перебор элементов множества. Мне попадался очень интересный лексографический алгоритм, который в теории (имхо) должен обеспечивать большую скорость генерации, но так как генерация комбинаций была лишь попутной для меня задачей разбираться не стал - ограничился рекурсией и убрал все лишнее. Массив исходных данных также в моем случае был вынужденной мерой, так как перестановки нужны были не для чисел или символов, а для вершин графа, которые были представлены то структурами то строками ТЗ. В итоге функция получилась довольно компактной и предельно универсальной.
А теперь мой вопрос:) Применение данной функции для оптимизации отображения графа на плоскости дало результат, но меня беспокоит быстродействие. Дело в том, что у меня граф рисуется довольно брутально - генерируются все возможные расположения вершин в узлах сетки и перебираются с пересчетом количества пересечений ребер графа. Если пересечений = 0, поиск прерывается, но в сложных графах такого практически не бывает и уже при не очень большом количестве вершин (15-20) пересчет длится 2-3 минуты на сервере. Больше половины этого времени занимает генерация комбинаций. Может Ваша реализация алгоритма быстрее моей? Как считаете?
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа