A parallel dynamic programming algorithm for unranking set partitions

• Autorzy: Kokosiński Z.

Warianty tytułu

PL

Równoległy algorytm programowania dynamicznego do konwersji liczb porządkowych w podziały zbioru

• Języki publikacji: EN

Abstrakty

EN

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.

PL

W artykule przedstawiono równoległy algorytm o złożoności O(n) dla wyznaczania podziału zbioru {1, ..., n} w reprezentacji Hutchinsona na podstawie jego liczby porządkowej. Prosty algorytm sekwencyjny opiera się na paradygmacie programowania dynamicznego. Algorytm równoległy łączy w sobie cechy programowania systolicznego i asocjacyjnego. Algorytm składa się z dwóch kroków. W pierwszej kolejności, za pomocą obliczeń systolicznych, wyznaczana jest tablica współczynników, zwanych liczbami Williamsona. Następnie, przez asocjacyjne wyznaczanie maksimum zbioru liczb, obliczanych jest n kolejnych elementów reprezentujących podział, każdy w czasie O(1).

Słowa kluczowe

EN

set partition; unranking algorithm; associative algorithm; parallel dynamic programming

PL

podział zbioru; algorytm konwersji liczby porządkowej w obiekt; algorytm asocjacyjny; równoległe programowanie dynamiczne

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2013
• Tom: R. 110, z. 3-AC
• Strony: 29--38
• Opis fizyczny: Bibliogr. 29 poz., wz., rys.

Twórcy

autor

Kokosiński Z.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• [1] Akl S.G., Parallel computation: models and methods, Prentice Hall, 1997, 475-509.
• [2] 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.
• [3] Butler J.T., Sasao T., Hardware index to set partition converter, Proc. ARC’2013, Lecture Notes in Computer Science, Vol. 7806, 2013, 72-83.
• [4] Djokič B. et al., A fast iterative algorithm for generating set partitions, The Computer Journal, Vol. 32, 1989, 281-282.
• [5] Djokič B. et al., Parallel algorithms for generating subset and set partitions, Proc SIGAL Int. Symposium on Algorithms, Tokyo 1990.
• [6] Er M.C., A fast algorithm for generating set partitions, The Computer Journal, Vol. 31, 1988, 283-284.
• [7] 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/
• [8] Hutchinson G., Partitioning algorithms for finite sets, Comm. ACM, Vol. 6, 1963, 613-614.
• [9] 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.
• [10] Kapralski A., Modelling arbitrary sets of combinatorial objects and their sequential and parallel generation, monograph, Studia Informatica, Vol. 21, No. 2 (40), 2000.
• [11] Kaye R., A Gray code for set partitions, Information Processing Letters, Vol. 5, 1976, 171-173.
• [12] Knuth D.E., The art of computer programming. Fundamental algorithms, Addison-Wesley, 3rd edition, 1997.
• [13] Knuth D.E., The art of computer programming, Pre-fascicle 3B. Generating all partitions, Addison-Wesley, 2004.
• [14] Kokosiński Z., On generation of permutations through decomposition of symmetric groups into cosets, BIT, Vol. 30, 1990, 583-591.
• [15] Kokosiński Z., Circuits generating combinatorial objects for sequential and parallel computer systems, Monografia 160, Politechnika Krakowska, Kraków 1993.
• [16] Kokosiński Z., Mask and pattern generation for associative supercom-puting, Proc. 12th Int. Conf. Applied Informatics AI’94, Annecy 1994, 324-326.
• [17] 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.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] Mirsky L., Transversal theory, Academic Press, 1971.
• [24] Semba I., An efficient algorithm for generating all partitions of the set {1, 2, ..., n}, Journal of Information Processing, Vol. 7, 1984, 41-42.
• [25] Stojmenovič I., An optimal algorithm for generating equivalence relations on a linear array of processors, BIT, Vol. 30, 1990, 424-436.
• [26] Stojmenovič I., On random and adaptive parallel generation of combinato-rial objects, Int. Journal of Computer Mathematics, Vol. 42, 1992, 125-135.
• [27] Tomic R.V., Quantized indexing: background information, Technical Report TR05-0625, 1st Works Corporation, June 25, 2005, 39.
• [28] Üç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.
• [29] Williamson S.G., Ranking algorithms for lists of partitions, SIAM J. of Computing, Vol. 5, 1976, 602-617.