Paper Info
Title
Enumeration, Counting, And Random Generation Of Ladder Lotteries
Abstract
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(3)) time. The random generation algorithm takes O(nb(3)) time for preprocess, and then it generates a ladder lottery in O(n + b) for each uniformly at random.
Year
DOI
Venue
2017
10.1587/transinf.2016FCP0015
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
Keywords
DocType
Volume
enumeration, counting, random generation, ladder lottery
Journal
E100D
Issue
ISSN
Citations 
3
1745-1361
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Katsuhisa Yamanaka16015.73
Shin-ichi Nakano224624.40