A parallel dynamic programming algorithm for unranking set partitions
cytuj
pobierz pliki
RIS BIB ENDNOTEWybierz format
RIS BIB ENDNOTEA parallel dynamic programming algorithm for unranking set partitions
Data publikacji: 16.09.2014
Czasopismo Techniczne, 2013, Automatyka Zeszyt 3-AC (11) 2013, s. 29 - 38
https://doi.org/10.4467/2353737XCT.14.055.3963Autorzy
A parallel dynamic programming algorithm for unranking set partitions
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.
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.
Informacje: Czasopismo Techniczne, 2013, Automatyka Zeszyt 3-AC (11) 2013, s. 29 - 38
Typ artykułu: Oryginalny artykuł naukowy
Tytuły:
A parallel dynamic programming algorithm for unranking set partitions
A parallel dynamic programming algorithm for unranking set partitions
Katedra Automatyki i Technik Informacyjnych, Wydział Elektrotechniki i Inżynierii Komputerowej, Politechnika Krakowska; Katedra Komputerowych Systemów Automatyki, Instytut Technologii Komputerowych, Automatyki i Metrologii, Uniwersytet Narodowy „Lvivska Politechnika”
Publikacja: 16.09.2014
Status artykułu: Otwarte
Licencja: Żadna
Udział procentowy autorów:
Korekty artykułu:
-Języki publikacji:
AngielskiLiczba wyświetleń: 2322
Liczba pobrań: 2223