2014年
Unranking of small combinations from large sets
Journal of Discrete Algorithms
- ,
- ,
- 巻
- 29
- 号
- C
- 開始ページ
- 8
- 終了ページ
- 20
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.jda.2014.07.004
- 出版者・発行元
- Elsevier B.V.
An unranking algorithm for a finite set Sis an algorithm that, given a number in {0, 1, ..., |S| -1}, returns an element of Sthat is associated with the number. We suppose that a number can be associated with any element in Sso long as distinct elements are associated with different numbers. A ranking algorithm is the reverse of an unranking algorithm. In this paper, we present an unranking algorithm for the set of all m-element subsets of an n-element set. Our algorithm runs with O(m3m+3)arithmetic operations, which is independent of nand hence is effective when nis large. We also show that it admits a ranking algorithm with the same running time.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.jda.2014.07.004
- ISSN : 1570-8667
- DBLP ID : journals/jda/ShimizuFN14
- J-Global ID : 201702203499902975
- SCOPUS ID : 84927973151