OPTIMIZATION OF PERMANENT DECOMPOSITION PROCEDURES USING PARALLELIZATION ALGORITHM
DOI:
https://doi.org/10.15588/1607-3274-2025-4-6Keywords:
parallelization, permanent decomposition, multi thread, algorithm, C#Abstract
Context. The problem of efficiently finding all permutations of a list of N elements is a key problem in many areas of computer science, such as combinatorics, optimization, cryptography, and machine learning. The object of the study was to analyze the procedure of permanent decomposition and propose an algorithm for its parallelization using modern features of working with threads in C#.
Objective. The goal of the work is the creation of the algorithm for parallelizing the generation of permutations using permanent decomposition processes.
Method. The main research method is the comparison of various algorithms with proposed parallelized algorithm, taking into account such criteria as accuracy and speed. Scientific works [10, 9, 17] present algorithms, including the regular permanent decomposition algorithm and the Johnson-Trotter algorithm. The Johnson-Trotter’s algorithm is one of the most effective, so it has been taken as some kind of benchmark.
It is worth mentioning that each paralleling process has its own disadvantages, including additional resources needed fot data
synchronization between threads. This can be minimized using both technical abilities of modern programming languages and optimization of the algorithm itself.
Results. The developed parallelized algorithm have improved performance of the regular permanent decomposition algorithm for solving the problem of finding all permutations.
Conclusions. The conducted experiments have confirmed the proposed parallelized algorithm’s version is better from a performance standpoint than the regular one. The prospects for further research may include the application of the parallelized version of the algorithm to some practical tasks and comparison of the results.
References
Akl S. G. The design and analysis of parallel algorithms. Englewood Cliffs, N.J : Prentice-Hall, 1989, 401 p.
Albahari J., Albahari B. C# 7.0 in a nutshell: the definitive reference. [S. l.], O’Reilly Media, 2017, 1088 p.
Cormen T. H., Stein C. , Rivest R. L. Introduction to algorithms. [S. l.], MIT Press, 2009, 1320 p.
Glynn D. G. The permanent of a square matrix [Electronic resource], European journal of combinatorics, 2010, Vol. 31, No. 7, pp. 1887–1891. Mode of access: https://doi.org/10.1016/j.ejc.2010.01.010
Gusfield D. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge [England], Cambridge University Press, 1999, 534 p.
Heap B. R. Permutations by interchanges [Electronic resource], The computer journal, 1963, Vol. 6, No. 3, pp. 293–298. Mode of access: https://doi.org/10.1093/comjnl/6.3.293
Herlihy M., Shavit N. Art of multiprocessor programming . [S. l.], Elsevier Science & Technology Books, 2011.
Johnson D. S., Garey. M. R. Computers and intractability: A guide to the theory of NP-completeness. New York, W.H. Freeman,1983,340p.
Johnson S. M. Generation of permutations by adjacent transposition [Electronic resource], Mathematics of computation, 1963, Vol. 17, No. 83, pp. 282–285. Mode of access: https://doi.org/10.1090/s0025-5718-1963-0159764-2
Knuth D. E. The art of computer programming: generating all tuples and permutations. 2nd ed. Upper Saddle River [etc.], Addison-Wesley, 2009, 128 p.
Let’s talk parallel programming with Stephen Toub [Electronic resource], Microsoft Learn. Mode of access: https://learn.microsoft.com/en-us/shows/on-dotnet/lets-talkparallel-programming-with-stephen-toub
McCool M., Reinders J., Robison A. Structured parallel programming: patterns for efficient computation. [S. l.], Elsevier Science & Technology Books, 2012, 432 p.
Richter J. CLR via C# . [S. l.] : Microsoft Press, 2012, 894 p.
Task-based asynchronous programming – .NET [Electronic resource], Microsoft Learn. Mode of access: https://learn.microsoft.com/enus/dotnet/standard/parallel-programming/task-basedasynchronous-programming
Task parallel library (TPL) – .NET [Electronic resource] // Microsoft Learn. Mode of access: https://learn.microsoft.com/ukua/dotnet/standard/parallel-programming/task-parallellibrary-tpl
Trotter H. F. Algorithm 115: perm [Electronic resource], Communications of the ACM, 1962, Vol. 5, No. 8, pp. 434– 435. Mode of access: https://doi.org/10.1145/368637.368660
Turbal Y. V., Babych S. V., Kunanets N. E. Permanent decomposition algorithm for the combinatorial objects generation [Electronic resource], Radio electronics, computer science, control, 2022, No. 4, P. 119. Mode of access: https://doi.org/10.15588/1607-3274-2022-4-10
Valiant L. G. The complexity of computing the permanent [Electronic resource], Theoretical computer science, 1979, Vol. 8, No. 2, pp. 189–201. Mode of access: https://doi.org/10.1016/0304-3975(79)90044-6
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Y. V. Turbal, A. Y. Moroziuk
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.
