Efficient Enumeration of All Ladder Lotteries and Its Application

• Yamanaka, Katsuhisa

• Nakano, Shin-ichi

• Matsui, Yasuko

• Uehara, Ryuhei

• Nakada, Kento

Abstract

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 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 π=(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.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/9176

Journal

• Theoretical Computer Science

  Theoretical Computer Science 411 (16-18), 1714-1722, 2010-01-13

  Elsevier

Keywords

• Enumeration algorithm
• Family tree
• Ladder lottery
• Pseudoline arrangement

Details

• CRID: 1050282812514965248
• NII Article ID: 120002511577
• ISSN: 03043975
• Web Site: http://hdl.handle.net/10119/9176
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles
  • KAKEN