A parallel algorithm for iterating partitions of a finite set into subsets of a given cardinality

A. M. Kovshov

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 16 (2020) no. 1, pp. 50-61

Résumé

The article describes an iterative algorithm for searching partitions of a finite set consisting of distinguishable elements into subsets of a given cardinality. The cardinalities of some subsets may be the same. The entire algorithm consists of two independent algorithms. The first algorithm for each element of the original set determines the cardinality of the subset that it will fall into when partitioning. To do this, subsets of the same cardinality are united into composite subsets. The elements of the original set are distributed among composite subsets. An index array is created to describe partitions. This array of indexes indicates which composite subset each element falls into. The length of the index array is equal to the cardinality of the original set. Each composite subset has its own index in the index array. Iterating over partitions of the original set into composite subsets is reduced to iterating over all index permutations in the index array. The second algorithm distributes elements within each composite subset over subsets of equal cardinalities. For each composite subset, an index array is created that describes which subset each element of the composite subset falls into. Iterating over all partitions of a composite subset over equally powerful subsets is reduced to iterating over-index permutations. Permutations must meet the following condition: the index value must not exceed the ordinal number of its place in the permutation. This avoids generating the same permutations. Permutations of all index arrays are iterated in lexicographic order. This construction of the algorithm allows to split the entire search into independent parts and use parallel calculations. An example is considered that shows the consistency of the algorithm and the acceleration of obtaining the result when using parallel calculations.

Détail

Keywords: exhaustive search algorithms, parallel computing.

Bibliographie

[1] V. Lipsky, Combinatorics for programmers, Mir, M., 1988, 213 pp. (In Russian)

[2] A. M. Kovshov, “The creating of shared search algorithms on the example of graph path searching”, Modern science, 12:1 (2018), 48–51

[3] B. Djocić, M. Miyakawa, S. Sekiguchi, I. Semba, I. Stojmenović, “A fast iterative algorithm for generating set partitions”, The Computer Journal, 32:3 (1989), 281–282 | DOI

[4] B. Djokić, M. Miyakawa, S. Sekiguchi, I. Semba, I. Stojmenović, “Parallel algorithms for generating subsets and set partitions”, International Symposium on Algorithms SIGAL 1990, 76–85

[5] G. H. Chen, M. S. Chern, “Parallel generation of permutations and combinations”, BIT Numerical Mathematics, 26 (1986), 277–283 | DOI | MR | Zbl

[6] Z. Kokosiński, “On generation of permutations through decomposition of symmetric groups into cosets”, BIT Numerical Mathematics, 30 (1990), 583–591 | DOI | MR | Zbl

[7] B. Uçar, Partitioning, matching, and ordering: Combinatorial scientific computing with matrices and tensors. Computer Science, ENS de Lyon, Lyon, 2019, 191 pp.

[8] M. Deveci, K. Kaya, B. Uçar, Ü. V. Çatalyürek, “Hypergraph partitioning for multiple communication cost metrics: Model and methods”, Journal of Parallel and Distributed Computing, 77:3 (2015), 69–83 | DOI

[9] H. Jiang, H. Feng, D. Zhu, “An 5/4-approximation algorithm for sorting permutations by short block moves”, Proceedings of the 25th International Symposium on Algorithms and Computation, 2014, 491–503 | MR | Zbl

[10] A. Alexandrino, G. Miranda, C. Lintzmayer, Z. Dias, “Approximation algorithms for sorting permutations by length-weighted short rearrangements”, Electronic Notes in Theoretical Computer Science, 346 (2019), 29–40 | DOI | MR

[11] G. R. Galvão, O. Lee, Z. Dias, “Sorting signed permutations by short operations”, Algorithms for Molecular Biology, 2015, no. 10, 1–17

[12] C. Crespelle, A. Perez, I. Todinca, “An $O(n^2)$ time algorithm for the minimal permutation completion problem”, Discrete Applied Mathematics, 254 (2019), 80–95 | DOI | MR | Zbl

[13] M. H. Albert, M.-L. Lackner, M. Lackner, V. Vatter, “The complexity of pattern matching for 321-avoiding and skew-merged permutations”, Discrete Mathematics Theoretical Computer Science, 18:2 (2016), 1–17 | MR

[14] M.-L. Lackner, M. Lackner, “A fast algorithm for permutation pattern matching based on alternating runs”, Algorithmica, 75:1 (2016), 84–117 | DOI | MR | Zbl

[15] A. Estaña, K. Molloy, M. Vaisset, N. Sibille, T. Siméon, P. Bernadó, J. Juan Cortés, “Hybrid parallelization of a multi-tree path search algorithm: Application to highly-flexible biomolecules”, Parallel Computing, 77 (2018), 84–100 | DOI | MR

[16] A. Oliveira, G. Fertin, U. Dias, Z. Dias, “Sorting signed circular permutations by super short operations”, Algorithms for Molecular Biology, 13:12 (2018), 13–18 | DOI

[17] V. P. Gergel, R. G. Strongin, Fundamentals of parallel computing for multiprocessor computing systems, Publ. of Lobachevskiy NNGU, Nizhniy Novgorod, 2003, 184 pp. (In Russian)

[18] V. V. Voevodin, Vl. V. Voevodin, Parallel computing, BHV-Petersburg Publ., Saint Petersburg, 2002, 608 pp. (In Russian)

[19] R. Stanley, Combinatorics for programmers, Mir, M., 1990, 440 pp. (In Russian) | MR