The Library
Combinatorial generation via permutation languages
Tools
Hartung, Elizabeth, Hoang, Hung, Mutze, Torsten and Williams, Aaron (2020) Combinatorial generation via permutation languages. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, United States, 5-8 Jan 2020. Published in: SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1214-1225. doi:10.5555/3381089.3381163
|
PDF
perm_soda_tikz.pdf - Accepted Version - Requires a PDF viewer. Download (655Kb) | Preview |
Official URL: https://dl.acm.org/doi/10.5555/3381089.3381163
Abstract
In this work we present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations.
This approach provides a unified view on many known results and allows us to prove many new ones.
In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element set by adjacent transpositions; the binary reflected Gray code to generate all $n$-bit strings by flipping a single bit in each step; the Gray code for generating all $n$-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an $n$-element ground set by element exchanges due to Kaye.
We present two distinct applications for our new framework:
The first main application is the generation of pattern-avoiding permutations, yielding new Gray codes for different families of permutations that are characterized by the avoidance of certain classical patterns, (bi)vincular patterns, barred patterns, Bruhat-restricted patterns, mesh patterns, monotone and geometric grid classes, and many others.
We thus also obtain new Gray code algorithms for the combinatorial objects that are in bijection to these permutations, in particular for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into $n$ rectangles subject to certain restrictions.
The second main application of our framework are lattice congruences of the weak order on the symmetric group~$S_n$.
Recently, Pilaud and Santos realized all those lattice congruences as $(n-1)$-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc.
Our algorithm generates the equivalence classes of each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian.
We thus also obtain a provable notion of optimality for the Gray codes obtained from our framework: They translate into walks along the edges of a polytope.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Gray codes, Congruence lattices , Quotient rings , Hamilton spaces | |||||||||
Journal or Publication Title: | SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||
Publisher: | SIAM | |||||||||
Official Date: | January 2020 | |||||||||
Dates: |
|
|||||||||
Page Range: | pp. 1214-1225 | |||||||||
DOI: | 10.5555/3381089.3381163 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Reuse Statement (publisher, data, author rights): | Published in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, published by the Society for Industrial and Applied Mathematics (SIAM) Copyright © 2020 by SIAM. Unauthorized reproduction of this article is prohibited. | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 5 October 2020 | |||||||||
Date of first compliant Open Access: | 5 October 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | 31st Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Salt Lake City, United States | |||||||||
Date(s) of Event: | 5-8 Jan 2020 | |||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year