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

05.06.15

Разработка - Универсальные функции

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

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

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

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

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

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

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

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

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

Всё!

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

комбинация комбинации перестановки сочетания комбинаторный алгоритм комбинаторика

См. также

Вставляем картинку из буфера обмена (платформа 1С 8.3.24)

Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

Задача: вставить картинку из буфера обмена на форму средствами платформы 1С.

1 стартмани

18.03.2024    2669    0    John_d    8    

54

GUID в 1С 8.3 - как с ними быть

Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Пришлось помучиться с GUID-ами немного, решил поделиться опытом, мало ли кому пригодится.

12.02.2024    4603    atdonya    22    

45

Переоткрытие внешних обработок

Универсальные функции Платформа 1С v8.3 Бесплатно (free)

На заключительных этапах, когда идет отладка или доработка интерфейса, необходимо много раз переоткрыть внешний объект. Вот один из способов автоматизации этого.

30.11.2023    3960    ke.92@mail.ru    16    

61

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023    8816    YA_418728146    6    

141

Печать непроведенных документов для УТ, КА, ERP. Настройка печати по пользователям, документам и печатным формам

Пакетная печать Печатные формы Адаптация типовых решений Универсальные функции Платформа 1С v8.3 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Россия Абонемент ($m)

Расширение для программ 1С:Управление торговлей, 1С:Комплексная автоматизация, 1С:ERP, которое позволяет распечатывать печатные формы для непроведенных документов. Можно настроить, каким пользователям, какие конкретные формы документов разрешено печатать без проведения документа.

2 стартмани

22.08.2023    2071    21    progmaster    7    

3

Расширение: Быстрые отборы через буфер [Alt+C] Копировать список, [Alt+V] Вставить список, [Ctrl+C] Копировать из файлов

Инструментарий разработчика Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 1С:Розница 2 1С:ERP Управление предприятием 2 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х 1С:Зарплата и Управление Персоналом 3.x Абонемент ($m)

Копирует в буфер значения из списков, из ячеек отчетов, таблиц, настроек списков, других отборов и вставляет в выбранную настройку отбора. Работает с Объект не найден. Работает как в одной так и между разными базами 1С. Использует комбинации [Alt+C] Копировать список, [Alt+V] Вставить список. Также для копирования данных используется стандартная [Ctrl+C] (например из открытого xls, mxl, doc и т.п. файла скопировать список наименований)

1 стартмани

13.10.2022    16143    133    sapervodichka    112    

129

Система контроля ведения учета [БСП]

Универсальные функции Механизмы типовых конфигураций БСП (Библиотека стандартных подсистем) Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

В данном материале рассмотрим типовой алгоритм подсистемы контроля учета БСП в конфигурациях на примерах.

18.07.2022    7242    quazare    8    

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

Там эта задача по-другому решена.
2. dusha0020 1103 08.06.15 15:28 Сейчас в теме
(1) Zeskord, К сожалению у меня в БСП такой функции нет.
3. rayastar 1459 08.06.15 19:19 Сейчас в теме
5. dusha0020 1103 09.06.15 08:26 Сейчас в теме
(3) rayastar, А почему слегка? Не качал Вашу работу, но подозреваю что суть алгоритма генерации комбинаций все та же - рекурсивный перебор элементов множества. Мне попадался очень интересный лексографический алгоритм, который в теории (имхо) должен обеспечивать большую скорость генерации, но так как генерация комбинаций была лишь попутной для меня задачей разбираться не стал - ограничился рекурсией и убрал все лишнее. Массив исходных данных также в моем случае был вынужденной мерой, так как перестановки нужны были не для чисел или символов, а для вершин графа, которые были представлены то структурами то строками ТЗ. В итоге функция получилась довольно компактной и предельно универсальной.
А теперь мой вопрос:) Применение данной функции для оптимизации отображения графа на плоскости дало результат, но меня беспокоит быстродействие. Дело в том, что у меня граф рисуется довольно брутально - генерируются все возможные расположения вершин в узлах сетки и перебираются с пересчетом количества пересечений ребер графа. Если пересечений = 0, поиск прерывается, но в сложных графах такого практически не бывает и уже при не очень большом количестве вершин (15-20) пересчет длится 2-3 минуты на сервере. Больше половины этого времени занимает генерация комбинаций. Может Ваша реализация алгоритма быстрее моей? Как считаете?
4. vova-1c 153 08.06.15 22:07 Сейчас в теме
На мой взгляд очень даже хорошо.
6. ichhh 1 25.04.17 16:07 Сейчас в теме
Дружище, не представляешь как я тебе благодарен! Огромное спасибо)) этот код мне десяток, другой часов сэкономил т.к. знаю про себя что алгоритмист я так себе.
ZDmitry83; +1 Ответить
7. user726666 02.08.18 10:25 Сейчас в теме
Реально выручил, спасибо!
8. dusha0020 1103 03.08.18 09:59 Сейчас в теме
9. user848614 09.08.19 12:28 Сейчас в теме
Спасибо, помогла функция)
10. tvssspb 22.01.20 14:50 Сейчас в теме
мне подошло на 100%
особое спасибо за параметры, благодаря чему всего 3 мин на внедрение! ))
11. druv 214 29.05.20 15:31 Сейчас в теме
Спасибо. Время сэкономил.
12. IVANTHESPACEBIKER 11.01.21 14:54 Сейчас в теме
Чуть модифицировал, чтобы была возможность получить комбинации без учета порядка ("1,2" и "2,1" не повторятся). М.б. кому сгодится.

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

Функция ЕстьЭлементБезУчетаПорядка(Результат, мРезультата)

	Для Каждого ТекРезультат Из мРезультата Цикл
		Если ТекРезультат.Количество() <> Результат.Количество() Тогда 
			Продолжить;
		КонецЕсли;
		
		флПолноеСовпадение = Истина;
		Для Каждого Элемент Из Результат Цикл
			Если ТекРезультат.Найти(Элемент) = Неопределено Тогда 
				флПолноеСовпадение = Ложь;
				Прервать;
			КонецЕсли;			
		КонецЦикла;
		
		Если флПолноеСовпадение Тогда 
			Возврат Истина;
		КонецЕсли;
		
	КонецЦикла;
	
	Возврат Ложь;

КонецФункции // ЕстьЭлементБезУчетаПорядка()

Показать
maikl007; zannv; Gisborn; dusha0020; +4 Ответить
13. binex 277 10.03.21 11:11 Сейчас в теме
Рефакторинг.


Функция Перестановки(мЭлементов, ДлинаПерестановки, 
						БезПовторов = Ложь, 
						Основание = Неопределено, 
						мРезультата = Неопределено, 
						ТекУровень = 0) Экспорт
    
    Если Основание = Неопределено Тогда Основание = Новый Массив КонецЕсли;
    Если мРезультата = Неопределено Тогда мРезультата = Новый Массив КонецЕсли;
    
	Для Каждого Элемент Из мЭлементов Цикл
		
		Если БезПовторов И Основание.Найти(Элемент) <> Неопределено Тогда
			Продолжить;
		КонецЕсли;
		
        Основание.Добавить(Элемент);
		
		Если ТекУровень < ДлинаПерестановки - 1 Тогда
        	мРезультата = Перестановки(мЭлементов, ДлинаПерестановки, БезПовторов, Основание, мРезультата, ТекУровень + 1);
		Иначе	
        	мРезультата.Добавить(Новый ФиксированныйМассив(Основание));
		КонецЕсли;
		
		Основание.Удалить(Основание.Количество() - 1);
		
    КонецЦикла;
	
    Возврат мРезультата;    
	
КонецФункции
Показать
sinichenko_alex; dctvghbdtn; dusha0020; +3 Ответить
14. Al777 22.03.21 00:04 Сейчас в теме
Большое спасибо за такую функцию! Чуть-чуть "допилил" для своих потребностей и вуаля... Получил то, что нужно. Время сэкономил нереально. Когда-то писал такую функцию, правда, ещё на 7.7, работала не ахти, как быстро.
15. cwant 5 24.02.22 22:19 Сейчас в теме
16. sinichenko_alex 178 16.09.22 15:28 Сейчас в теме
Рефакторинг

Процедура КакПользоваться()
	
	Основной = Новый Массив;
	Для Индекс = 0 По 6 Цикл
		Основной.Добавить(Индекс);
	КонецЦикла;
	
	сткПараметры = Новый Структура;
	сткПараметры.Вставить("мЭлементов", Основной);
	сткПараметры.Вставить("ДлинаПерестановки", Основной.Количество());
	сткПараметры.Вставить("БезПовторов", Истина);
	сткПараметры.Вставить("Основание", Новый Массив);
	сткПараметры.Вставить("мРезультата", Новый Массив);
	
	Рез = Перестановки(сткПараметры);
		
КонецПроцедуры

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

Столкнулся с подобной задачей для поиска по произвольной комбинации слов контекста.
Вроде простая идея, а затруднился. Закопался. Старею, наверное. Забыл комбинаторику.

Решил поискать, нашел здесь.

Спасибо.

Однозначно, плюс.
Оставьте свое сообщение