Efficient enumeration of all ladder lotteries and its application

作     者：Yamanaka, Katsuhisa Nakano, Shin-ichi Matsui, Yasuko Uehara, Ryuhei Nakada, Kento 

作者机构：Univ Electrocommun Grad Sch Informat Syst Tokyo 1828585 Japan Gunma Univ Dept Comp Sci Gunma 3768515 Japan Tokai Univ Dept Math Sci Kanagawa 2591292 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Wakkanai Hokusei Gakuen Univ Fac Integrated Media Wakkanai Hokkaido 0970013 Japan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2010年第411卷第16-18期

页      面：1714-1722页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Enumeration algorithm Family tree Ladder lottery Pseudoline arrangement 

摘      要：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 pi is optimal if L has the minimum number of horizontal lines among the ladder lotteries corresponding to pi. In this paper we show that for any two optimal ladder lotteries L-1 and L-2 of a permutation, there exists a sequence of local modifications which transforms L-1 into L-2. We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting pi = (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. (C) 2010 Elsevier B.V. All rights reserved.