The Library
Star transposition Gray codes for multiset permutations
Tools
Gregor, Petr, Mutze, Torsten and Merino, Arturo (2022) Star transposition Gray codes for multiset permutations. In: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Marseille, 15-18 Mar 2022. Published in: Proceedings of STACS 2022, 219 34:1-34:14. ISBN 9783959772228. doi:10.4230/LIPIcs.CVIT.2016.23 ISSN 1868-8969.
|
PDF
WRAP-Star-transposition-Gray-codes-multiset-permutations-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (2309Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.CVIT.2016.23
Abstract
Given integers $k\geq 2$ and $a_1,\ldots,a_k\geq 1$, let $\ba:=(a_1,\ldots,a_k)$ and $n:=a_1+\cdots+a_k$.
An $\ba$-multiset permutation is a string of length~$n$ that contains exactly $a_i$ symbols~$i$ for each $i=1,\ldots,k$.
In this work we consider the problem of exhaustively generating all $\ba$-multiset permutations by star transpositions, i.e., in each step, the first entry of the string is transposed with any other entry distinct from the first one.
This is a far-ranging generalization of several known results.
For example, it is known that permutations ($a_1=\cdots=a_k=1$) can be generated by star transpositions, while combinations ($k=2$) can be generated by these operations if and only if they are balanced ($a_1=a_2$), with the positive case following from the middle levels theorem.
To understand the problem in general, we introduce a parameter~$\Delta(\ba):=n-2\max\{a_1,\ldots,a_k\}$ that allows us to distinguish three different regimes for this problem.
We show that if $\Delta(\ba)<0$, then a star transposition Gray code for $\ba$-multiset permutations does not exist.
We also construct such Gray codes for the case $\Delta(\ba)>0$, assuming that they exist for the case~$\Delta(\ba)=0$.
For the case~$\Delta(\ba)=0$ we present some partial positive results.
Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams.
In particular, we prove that the middle levels graph is Hamilton-laceable.
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, Permutations , Combinations , Combinatorial analysis, Computer science -- Mathematics | ||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||
Journal or Publication Title: | Proceedings of STACS 2022 | ||||||||||||
Publisher: | LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik | ||||||||||||
ISBN: | 9783959772228 | ||||||||||||
ISSN: | 1868-8969 | ||||||||||||
Official Date: | 9 March 2022 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 219 | ||||||||||||
Page Range: | 34:1-34:14 | ||||||||||||
DOI: | 10.4230/LIPIcs.CVIT.2016.23 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 6 January 2022 | ||||||||||||
Date of first compliant Open Access: | 7 January 2022 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) | ||||||||||||
Type of Event: | Workshop | ||||||||||||
Location of Event: | Marseille | ||||||||||||
Date(s) of Event: | 15-18 Mar 2022 | ||||||||||||
Related URLs: | |||||||||||||
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