For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Enumeration, Counting, and Random Generation of Ladder Lotteries
Katsuhisa YAMANAKA Shin-ichi NAKANO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2017/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
enumeration, counting, random generation, ladder lottery,
Full Text: PDF(586KB)
>>Buy this Article
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(nb3) time. The random generation algorithm takes O(nb3) time for preprocess, and then it generates a ladder lottery in O(n + b) for each uniformly at random.