A parallel dynamic programming algorithm for unranking set partitions

• Authors: Zbigniew Kokosiński
• Languages of publication: PL

Abstracts

PL

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.

Keywords

PL

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

• Publisher: [unknown2]
• Journal: Czasopismo Techniczne
• Year: -

Dates

online

2015-04-21

Contributors

author

Zbigniew Kokosiński