論文

査読有り
2014年

Unranking of small combinations from large sets

Journal of Discrete Algorithms
  • Toshihiro Shimizu
  • ,
  • Takuro Fukunagaa
  • ,
  • Hiroshi Nagamochi

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.

リンク情報
DOI
https://doi.org/10.1016/j.jda.2014.07.004
DBLP
https://dblp.uni-trier.de/rec/journals/jda/ShimizuFN14
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201702203499902975
URL
http://dblp.uni-trier.de/db/journals/jda/jda29.html#journals/jda/ShimizuFN14
ID情報
  • DOI : 10.1016/j.jda.2014.07.004
  • ISSN : 1570-8667
  • DBLP ID : journals/jda/ShimizuFN14
  • J-Global ID : 201702203499902975
  • SCOPUS ID : 84927973151

エクスポート
BibTeX RIS