IEICE TRANSACTIONS on Information
Enumeration, Counting, and Random Generation of Ladder Lotteries
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.3 pp.444-451
- Publication Date
- 2017/03/01
- Publicized
- 2016/12/21
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2016FCP0015
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
- Category
Authors
Katsuhisa YAMANAKA
Iwate University
Shin-ichi NAKANO
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Katsuhisa YAMANAKA, Shin-ichi NAKANO, "Enumeration, Counting, and Random Generation of Ladder Lotteries" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 3, pp. 444-451, March 2017, doi: 10.1587/transinf.2016FCP0015.
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(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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016FCP0015/_p
Copy
@ARTICLE{e100-d_3_444,
author={Katsuhisa YAMANAKA, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={Enumeration, Counting, and Random Generation of Ladder Lotteries},
year={2017},
volume={E100-D},
number={3},
pages={444-451},
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(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.},
keywords={},
doi={10.1587/transinf.2016FCP0015},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Enumeration, Counting, and Random Generation of Ladder Lotteries
T2 - IEICE TRANSACTIONS on Information
SP - 444
EP - 451
AU - Katsuhisa YAMANAKA
AU - Shin-ichi NAKANO
PY - 2017
DO - 10.1587/transinf.2016FCP0015
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2017
AB - 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.
ER -
English
