Coding Ladder Lotteries
スポンサーリンク
概要
- 論文の詳細を見る
A ladder lottery, known as the "Amidakuji" in Japan, is a common way to choose a permutation randomly. In this paper, we consider a problem of coding an optimal ladder lotteries. We first propose two codes for an optimal ladder lottery. The more compact codes among them needs at most n + 2b - 1 bits, where n is the number of vertical lines and b is the number of horizontal lines in an optimal ladder lottery. As a by-product of this result, we obtain an upper bound on the number of optimal ladder lotteries with n vertical lines and b horizontal lines. Furthermore we improve the code and experimentally show that the average length of the improved code is more compact.
- 2012-10-26
著者
-
Katsuhisa Yamanaka
Graduate School Of Information Systems University Of Electro-communications.
-
Katsuhisa Yamanaka
Department of Electrical Engineering and Computer Science, Iwate University.
-
Yasuaki Nishitani
Department Of Electrical Engineering And Computer Science Iwate University
-
Tomoki Aiuchi
Department of Electrical Engineering and Computer Science, Iwate University|Currently with Leadkonan
-
Takashi Hirayama
Department of Electrical Engineering and Computer Science, Iwate University
-
Tomoki Aiuchi
Department Of Electrical Engineering And Computer Science Iwate University|currently With Leadkonan
-
Katsuhisa Yamanaka
Department Of Electrical Engineering And Computer Science Iwate University
-
Takashi Hirayama
Department Of Electrical Engineering And Computer Science Iwate University
関連論文
- Enumerating All Rooted Trees Including k Leaves
- Computational Complexities of University Interview Timetabling
- Random Generation and Enumeration of Proper Interval Graphs
- Efficient Enumeration of All Ladder Lotteries with k Bars
- Efficient Enumeration of All Pseudoline Arrangements
- A Compact Encoding of Rectangular Drawings with Edge Lengths
- Approximating the path-distance-width for k-cocomparability graphs
- Coding Ladder Lotteries
- Another Optimal Binary Representation of Mosaic Floorplans
- Uniformly Random Generation of Floorplans