http://swrc.ontoware.org/ontology#TechnicalReport
Coding Ladder Lotteries
en
Department of Electrical Engineering and Computer Science, Iwate University／Currently with Leadkonan
Department of Electrical Engineering and Computer Science, Iwate University
Department of Electrical Engineering and Computer Science, Iwate University
Department of Electrical Engineering and Computer Science, Iwate University
Tomoki Aiuchi
Katsuhisa Yamanaka
Takashi Hirayama
Yasuaki Nishitani
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.
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.
AN1009593X
研究報告アルゴリズム（AL）
2012-AL-142
10
1-6
2012-10-26