Permanent decomposition algorithm for the combinatorial objects generation

Abstract

EN: Context. The problem of generating vectors consisting of different representatives of a given set of sets is considered. Such problems arise, in particular, in scheduling theory, when scheduling appointments. A special case of this problem is the problem of generating permutations. Objective. Problem is considered from the point of view of a permanent approach and a well-known one, based on the concept of lexicographic order. Method. In many tasks, it becomes necessary to generate various combinatorial objects: permutations, combinations with and without repetitions, various subsets. In this paper we consider a new approach to the combinatorial objects generation, which is based on the procedure of the permanent decomposition. Permanent is built for the special matrix of incidence. The main idea of this approach is including to the process of the algebraic permanent decomposition by row additional function for the column identifiers writing into corresponding data structures. In this case, the algebraic permanent in not calculated, but we get a specific recursive algorithm for generating a combinatorial object. The computational complexity of this algorithm is analyzed. Results. It is investigated a new approach to the generation of complex combinatorial objects, based on the procedure of decomposition of the modified permanent of the incidence matrix by line with memorization of index elements. Conclusions. The permanent algorithms of the combinatorial objects generation is investigated. The complexity of our approach in the case of permutation is compared with the lexicographic algorithm and the Johnson-Trotter algorithm. The obtained results showed that our algorithm belongs to the same complexity class as the lexicographic algorithm and the Johnson-Trotter method. Numerical results confirmed the effectiveness of our approach. UK: Актуальність. Розглядається задача генерування векторів, що складаються з різних представників заданої множини. Такі проблеми виникають, зокрема, в теорії складання розкладів, при плануванні зустрічей. Окремим випадком цієї задачі є задача генерування перестановок. Мета роботи – розглянути проблему з точки зору постійного та загальновідомого підходу, виходячи з концепції лексикографічного порядку. Метод. У багатьох завданнях виникає необхідність генерувати різноманітні комбінаторні об’єкти: перестановки, комбінації з повтореннями і без них, різноманітні підмножини. У цій роботі розглядається новий підхід до генерації комбінаторних об’єктів, який базується на процедурі постійної декомпозиції. Перманент будується для спеціальної матриці інцидентності. Основна ідея цього підходу полягає в включенні до процесу алгебраїчної перманентної декомпозиції за допомогою додаткової функції рядка для запису ідентифікаторів стовпців у відповідні структури даних. У цьому випадку алгебраїчний перманент не обчислюється, а отримуємо конкретний рекурсивний алгоритм генерації комбінаторного об’єкта. Проаналізовано обчислювальну складність цього алгоритму. Результати. В межах PD-підходу розглянуто задачі генерації комбінаторних об’єктів, зокрема, перестановок. Досліджено обчислювальну складність запропонованих алгоритмів у порівнянні з відомими підгодами. Розглянуто варіант програмної реалізації розроблених алгоритмів. Висновки. У роботі розглянуто новий підхід до генерації складних комбінаторних об’єктів, що грунтується на процедурі декомпозиції модифікованого перманенту матриці інцидентності за рядком із запам’ятовуванням елементів індексу. Специфіка цього підходу полягає в тому, що певні додаткові умови, що накладаються на відповідні системи різних представників, враховуються на етапі процедур декомпозиції. Досліджено складність розглянутих алгоритмів. У разі більш складних варіантів матриці інцидентності пропонується відповідна модифікація поняття перманенту і, відповідно, процедура його декомпозиції .