Problem of lexicographic unranking of a permutation is in NC

B.Y. Wu; C.Y. Tang

Journal article

Problem of lexicographic unranking of a permutation is in NC

Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering, Vol.18(4), pp.348-352

07/1994

Abstract

Engineering (all)

A parallel lexicographic unranking algorithm of a permutation of r out n objects is developed in this paper. The time complexity of our algorithm is O(rlogr/N+logrloglogN) on the CREW PRAM model, where N is the number of processors. This result shows that the problem for lexicographic unranking of a permutation is in NC. In particular, when N=1, our algorithm is also the most efficient sequential algorithm.

Metrics

1 Record Views

Details

Title: Problem of lexicographic unranking of a permutation is in NC
Translated title: Problem of lexicographic unranking of a permutation is in NC
Creators - without role: B.Y. Wu - Natl Tsing Hua Univ
C.Y. Tang - Natl Tsing Hua Univ
Publication Details: Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering, Vol.18(4), pp.348-352
Identifiers: 9957769859506774
Academic Unit: National Tsing Hua University
Language: English
Resource Type: Journal article

Problem of lexicographic unranking of a permutation is in NC

Abstract

Related links

Metrics

Details

National Tsing Hua University Social media