Efficient enumeration of all ladder lotteries and its application

Abstract: A ladder lottery, known as “Amidakuji” in Japan, is a common way to choose a permutation randomly. A ladder lottery corresponding to a given permutation is optimal if has the minimum number of horizontal lines among the ladder lotteries corresponding to . In this paper we show that for any two optimal ladder lotteries and of a permutation, there exists a sequence of local modifications which transforms into . We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting , the algorithm enumerates all arrangements of pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of pseudolines for each . [Copyright &y& Elsevier]