Efficient enumeration of all ladder lotteries and its application

A ladder lottery, known as “Amidakuji” in Japan, is a common way to choose a permutation randomly. A ladder lottery L corresponding to a given permutation π is optimal if L 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 L1 and L2 of a permutation, there exists a sequence of local modifications which transforms L1 into L2. We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting π=(n,n−1,…,1), the algorithm enumerates all arrangements of n pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of n pseudolines for each n≤11.