2022-09-30T22:14:11Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000861412020-04-01T00:33:29Z01164:02592:06670:06899
Coding Ladder LotteriesCoding Ladder Lotteriesenghttp://id.nii.ac.jp/1001/00086127/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=86141&item_no=1&attribute_id=1&file_no=1Copyright (c) 2012 by the Information Processing Society of JapanDepartment of Electrical Engineering and Computer Science, Iwate University／Currently with LeadkonanDepartment of Electrical Engineering and Computer Science, Iwate UniversityDepartment of Electrical Engineering and Computer Science, Iwate UniversityDepartment of Electrical Engineering and Computer Science, Iwate UniversityTomoki, AiuchiKatsuhisa, YamanakaTakashi, HirayamaYasuaki, NishitaniA 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-14210162012-10-262012-10-16