Main content

Amidakuji: Gray Code Algorithms for Listing Ladder Lotteries

Show full item record

Title: Amidakuji: Gray Code Algorithms for Listing Ladder Lotteries
Author: Di Salvo, Patrick
Department: School of Computer Science
Program: Computer Science
Advisor: Sawada, Joe
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 $O(1)$ time. We provide an $O(n^2)$ amortized algorithm for creating a specific ladder corresponding to a specific permutation. We provide an $O(1)$ amortized algorithm for listing $n!$ canonical ladders by adding or removing a bar. Finally, we provide a Gray code for listing $n!$ ladders ordered by the number of bars.
URI: https://hdl.handle.net/10214/26298
Date: 2021-08
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.


Files in this item

Files Size Format View
DiSalvo_Patrick_202108_MSc.pdf 609.5Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record