IEICE TRANSACTIONS on Fundamentals
Efficient Enumeration of All Ladder Lotteries with k Bars
Summary :
A ladder lottery, known as the “Amidakuji” in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines is known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1163-1170
- Publication Date
- 2014/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1163
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- 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, "Efficient Enumeration of All Ladder Lotteries with k Bars" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1163-1170, June 2014, doi: 10.1587/transfun.E97.A.1163.
Abstract: A ladder lottery, known as the “Amidakuji” in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines is known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1163/_p
Copy
@ARTICLE{e97-a_6_1163,
author={Katsuhisa YAMANAKA, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Enumeration of All Ladder Lotteries with k Bars},
year={2014},
volume={E97-A},
number={6},
pages={1163-1170},
abstract={A ladder lottery, known as the “Amidakuji” in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines is known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.},
keywords={},
doi={10.1587/transfun.E97.A.1163},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Efficient Enumeration of All Ladder Lotteries with k Bars
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1163
EP - 1170
AU - Katsuhisa YAMANAKA
AU - Shin-ichi NAKANO
PY - 2014
DO - 10.1587/transfun.E97.A.1163
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - A ladder lottery, known as the “Amidakuji” in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines is known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.
ER -
English
