Show simple item record

dc.contributor.author
Hartung, Elizabeth
dc.contributor.author
Hoang, Hung P.
dc.contributor.author
Mütze, Torsten
dc.contributor.author
Williams, Aaron
dc.date.accessioned
2021-08-10T07:31:44Z
dc.date.available
2020-08-20T09:42:18Z
dc.date.available
2020-09-07T12:16:39Z
dc.date.available
2021-08-10T07:25:28Z
dc.date.available
2021-08-10T07:30:31Z
dc.date.available
2021-08-10T07:31:44Z
dc.date.issued
2020-01
dc.identifier.other
10.1137/1.9781611975994.74
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/432109
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
Society for Industrial and Applied Mathematics
en_US
dc.title
Combinatorial generation via permutation languages
en_US
dc.type
Conference Paper
dc.date.published
2020-01-05
ethz.book.title
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms
en_US
ethz.pages.start
1214
en_US
ethz.pages.end
1225
en_US
ethz.event
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
en_US
ethz.event.location
Salt Lake City, UT, USA
en_US
ethz.event.date
January 5-8, 2020
en_US
ethz.identifier.wos
ethz.publication.place
Philadelphia, PA
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo::08817 - Gärtner, Bernd (Tit.-Prof.)
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
ethz.date.deposited
2020-08-20T09:42:23Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-08-10T07:25:41Z
ethz.rosetta.lastUpdated
2022-03-29T11:00:03Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Combinatorial%20generation%20via%20permutation%20languages&rft.date=2020-01&rft.spage=1214&rft.epage=1225&rft.au=Hartung,%20Elizabeth&Hoang,%20Hung%20P.&M%C3%BCtze,%20Torsten&Williams,%20Aaron&rft.genre=proceeding&rft_id=info:doi/10.1137/1.9781611975994.74&rft.btitle=SODA%20'20:%20Proceedings%20of%20the%20Thirty-First%20Annual%20ACM-SIAM%20Symposium%20on%20Discrete%20Algorithms
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record