Enumeration, Counting, and Random Generation of Ladder Lotteries

• YAMANAKA Katsuhisa

  Faculty of Science and Engineering, Iwate University

• NAKANO Shin-ichi

  School of Science and Technology, Gunma University

抄録

A ladder lottery, known as “Amidakuji” in Japan, is one of the most popular lotteries. In this paper, we consider the problems of enumeration, counting, and random generation of the ladder lotteries. For given two positive integers n and b, we give algorithms of enumeration, counting, and random generation of ladder lotteries with n lines and b bars. The running time of the enumeration algorithm is O(n + b) time for each. The running time of the counting algorithm is O(nb³) time. The random generation algorithm takes O(nb³) time for preprocess, and then it generates a ladder lottery in O(n + b) for each uniformly at random.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E100.D (3), 444-451, 2017

  一般社団法人 電子情報通信学会

キーワード

• enumeration
• counting
• random generation
• ladder lottery

詳細情報

• CRID: 1390001204378226816
• NII論文ID: 130005397935
• DOI: 10.1587/transinf.2016fcp0015
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E100.D/3/E100.D_2016FCP0015/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可