Abstract
A ladder lottery of a permutation \(\pi \) of \(\{1,2,\ldots ,n\}\) is a network with n vertical lines and zero or more horizontal lines each of which connects two consecutive vertical lines and corresponds to an adjacent transposition. The composition of all the adjacent transpositions coincides with \(\pi \). A cyclic ladder lottery of \(\pi \) is a ladder lottery of \(\pi \) that is allowed to have horizontal lines between the first and last vertical lines. A cyclic ladder lottery of \(\pi \) is optimal if it has the minimum number of horizontal lines. In this paper, for optimal cyclic ladder lotteries, we consider the reconfiguration and enumeration problems. First, we investigate the two problems when a permutation \(\pi \) and its optimal displacement vector \(\boldsymbol{x}\) are given. Then, we show that any two optimal cyclic ladder lotteries of \(\pi \) and \(\boldsymbol{x}\) are always reachable under braid relations and one can enumerate all the optimal cyclic ladder lotteries in polynomial delay. Next, we consider the two problems for optimal displacement vectors when a permutation \(\pi \) is given. Then, we present a characterization of the length of a shortest reconfiguration sequence of two optimal displacement vectors and show that there exists a constant-delay algorithm that enumerates all the optimal displacement vectors of \(\pi \).
This work was supported by JSPS KAKENHI Grant Numbers JP18H04091, JP20H05793, JP20K14317, and JP22K17849.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
An arrangement is simple if no three pseudolines have a common intersection point. In this paper, we consider only simple arrangements of pseudolines.
- 2.
A pseudoline in the Euclidean plane is a y-monotone curve extending from positive infinity to negative infinity.
- 3.
The contraction is originally proposed by Jerrum [5].
References
Avis, D., Fukuda, K.: Reverse search for enumeration. Discret. Appl. Math. 65(1–3), 21–46 (1996)
Björner, A., Brenti, F.: Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, vol. 231. Springer, New York (2005)
Dumitrescu, A., Mandal, R.: New lower bounds for the number of pseudoline arrangements. J. Comput. Geom. 11(1), 60–92 (2020). https://doi.org/10.20382/jocg.v11i1a3
Felsner, S., Valtr, P.: Coding and counting arrangements of pseudolines. Discret. Comput. Geom. 46, 405–416 (2011)
Jerrum, M.R.: The complexity of finding minimum-length generator sequence. Theor. Comput. Sci. 36, 265–289 (1985)
Yamanaka, K., Horiyama, T., Wasa, K.: Optimal reconfiguration of optimal ladder lotteries. Theor. Comput. Sci. 859, 57–69 (2021). https://doi.org/10.1016/j.tcs.2021.01.009
Yamanaka, K., Nakano, S., Matsui, Y., Uehara, R., Nakada, K.: Efficient enumeration of all ladder lotteries and its application. Theor. Comput. Sci. 411, 1714–1722 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Nozaki, Y., Wasa, K., Yamanaka, K. (2023). Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries. In: Hsieh, SY., Hung, LJ., Lee, CW. (eds) Combinatorial Algorithms. IWOCA 2023. Lecture Notes in Computer Science, vol 13889. Springer, Cham. https://doi.org/10.1007/978-3-031-34347-6_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-34347-6_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34346-9
Online ISBN: 978-3-031-34347-6
eBook Packages: Computer ScienceComputer Science (R0)