En steglotteri, känd som "Amidakuji" i Japan, är ett vanligt sätt att välja en permutation slumpmässigt. En steglott L som motsvarar en given permutation π är optimal om L har det minsta antalet horisontella linjer bland steglotterier som motsvarar π. I detta papper visar vi att för två optimala steglotterier L 1 och L 2 av en permutation, finns det en sekvens av lokala modifieringar som omvandlar L 1 till L 2. Vi ger också en algoritm för att räkna upp alla optimala steglotterier av en given permutation. Genom att ställa in π = (n, n − 1,.., 1) räknar algoritmen upp alla arrangemang av n pseudolines effektivt. Genom att implementera algoritmen beräknar vi antalet arrangemang av n pseudolines för varje n ≤ 11.
För det tredje, en stege lotteri av omvänd permutation (n, n − 1,.., 1) motsvarar en pseudoline arrangemang i diskret geometri REF.
Efficient enumeration of all ladder lotteries and its application
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}