A parallel dynamic programming algorithm for unranking set partitions

Zbigniew Kokosiński

Abstrakt

In this paper, an O(n) parallel algorithm is presented for unranking set partitions in Hutchinson’s representation. A simple sequential algorithm is derived on the basis of a dynamic programming paradigm. In the parallel algorithm, processing is performed in a dedicated parallel architecture combining certain systolic and associative features. The algorithm consists of two phases. In the first phase, a coefficient table is created by systolic computations. Then, n subsequent elements of a partition codeword are computed, in O(1) time each, through associative search operations.

Słowa kluczowe: set partition, unranking algorithm, associative algorithm, parallel dynamic programming
References

Akl S.G., Parallel computation: models and methods, Prentice Hall, 1997, 475-509.

Akl S.G., Stojmenovič I., Generating combinatorial objects on a linear array of processors, [in:] Zomaya A.Y. (editor): Parallel Computing: Paradigms and Applications, Int. Thompson Comp. Press, 1996, 639-670.

Butler J.T., Sasao T., Hardware index to set partition converter, Proc. ARC’2013, Lecture Notes in Computer Science, Vol. 7806, 2013, 72-83.

Djokič B. et al., A fast iterative algorithm for generating set partitions, The Computer Journal, Vol. 32, 1989, 281-282.

Djokič B. et al., Parallel algorithms for generating subset and set partitions, Proc SIGAL Int. Symposium on Algorithms, Tokyo 1990.

Er M.C., A fast algorithm for generating set partitions, The Computer Journal, Vol. 31, 1988, 283-284.

Hankin R.K.S., West L.J., Set partitions, J. of Statistical Software, Vol. 23, Code Snippet 2 (December 2007), available at: http://www.jstatsoft.org/

Hutchinson G., Partitioning algorithms for finite sets, Comm. ACM, Vol. 6, 1963, 613-614.

Kapralski A., New methods for the generation of permutations, combinations and other combinatorial objects in parallel, Journal of Parallel and Distributed Computing, Vol. 17, 1993, 315-326.

Kapralski A., Modelling arbitrary sets of combinatorial objects and their sequential and parallel generation, monograph, Studia Informatica, Vol. 21, No. 2 (40), 2000.

Kaye R., A Gray code for set partitions, Information Processing Letters, Vol. 5, 1976, 171-173.

Knuth D.E., The art of computer programming. Fundamental algorithms, Addison- Wesley, 3rd edition, 1997.

Knuth D.E., The art of computer programming, Pre-fascicle 3B. Generating all partitions, Addison-Wesley, 2004.

Kokosiński Z., On generation of permutations through decomposition of symmetric groups into cosets, BIT, Vol. 30, 1990, 583-591.

Kokosiński Z., Circuits generating combinatorial objects for sequential and parallel computer systems, Monografia 160, Politechnika Krakowska, Kraków 1993.

Kokosiński Z., Mask and pattern generation for associative supercom-puting, Proc. 12th Int. Conf. Applied Informatics AI’94, Annecy 1994, 324-326.

Kokosiński Z., Algorithms for unranking combinations and their applica-tion, Proc. 7th Int. Conf. Parallel and Distributed Computing and Systems PDCS’95, Washington D.C., USA, 1995, 216-224.

Kokosiński Z., Unranking combinations in parallel, Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications PDPTA’96, Sunnyvale, CA, USA, Vol. I, 1996, 79-82.

Kokosiński Z., On parallel generation of set partitions in associative processor architectures, Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications PDPTA’99, Las Vegas, USA, Vol. III, 1999, 1257-1262.

Kokosiński Z., A parallel dynamic programming algorithm for unranking t-ary trees, Proc. PPAM’2003, Lecture Notes in Computer Science, Vol. 3019, 2004, 255-260.

Kokosiński Z., A new algorithm for generation of exactly m-block set partitions in associative model, Proc. PPAM’2005, Lecture Notes in Computer Science, Vol. 3911, 2006, 67-74.

Kokosiński Z., Parallel enumeration of t-ary trees in ASC SIMD model, Int. J. Computer Science and Network Security, Vol. 11, No. 12, 2011, 38-49.

Mirsky L., Transversal theory, Academic Press, 1971.

Semba I., An efficient algorithm for generating all partitions of the set {1, 2, ..., n}, Journal of Information Processing, Vol. 7, 1984, 41-42.

Stojmenovič I., An optimal algorithm for generating equivalence relations on a linear array of processors, BIT, Vol. 30, 1990, 424-436.

Stojmenovič I., On random and adaptive parallel generation of combinato-rial objects, Int. Journal of Computer Mathematics, Vol. 42, 1992, 125-135.

Tomic R.V., Quantized indexing: background information, Technical Report TR05-0625, 1st Works Corporation, June 25, 2005, 39.

Üçoluk G., A method for chromosome handling of r-permutations of n-element set in genetic algorithms, Proc. 4th Int. Conf. on Evolutionary Compu-ting ICEC’97, Indianapolis, USA, 55-58, 1997.

Williamson S.G., Ranking algorithms for lists of partitions, SIAM J. of Computing, Vol. 5, 1976, 602-617.