A parallel dynamic programming algorithm for unranking set partitions
Variant of the title
Równoległy algorytm programowania dynamicznego do konwersji liczb porządkowych w podziały zbioru
Author
Kokosiński, Zbigniew
Published in
Technical Transactions
Numbering
Y. 110, iss. 3-AC
Pages
29-38
Release date
2013
Place of publication
Kraków
Publisher
Wydawnictwo PK
Language
English
Keywords
set partition, unranking algorithm, associative algorithm, parallel dynamic programming
podział zbioru, algorytm konwersji liczby porządkowej w obiekt, algorytm asocjacyjny, równoległe programowanie dynamiczne
Abstract
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.
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).
PKT classification
390000 Automatyka
Department
Faculty of Electrical and Computer Engineering
License
Licencja PK
Access rights
Zasób dostępny dla wszystkich
Cookies or other similar solutions are used on the page. Take a look at privacy policy to get to know the details.