Amidakuji: Gray Code Algorithms for Listing Ladder Lotteries
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We provide a Gray code for listing ladder lotteries in which successive ladders differ by the addition/removal of a single bar or the relocation of a bar. Ladder lotteries are an abstract mathematical object which correspond to permutations. They are a network of vertical lines and horizontal bars, which induce transpositions on elements in a specific permutation when the lines cross. Ladder lotteries are of interest to the field of theoretical computer science because of their relationship with other mathematical objects such as primitive sorting networks. To list ladder lotteries, we define a function that calculates the location for any bar in the data structure in