Gregor, Petr ;
Mütze, Torsten ;
Merino, Arturo
Star Transposition Gray Codes for Multiset Permutations
Abstract
Given integers k ≥ 2 and a_1,…,a_k ≥ 1, let a: = (a_1,…,a_k) and n: = a_1+⋯+a_k. An amultiset permutation is a string of length n that contains exactly a_i symbols i for each i = 1,…,k. In this work we consider the problem of exhaustively generating all amultiset 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 farranging generalization of several known results. For example, it is known that permutations (a_1 = ⋯ = 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 Δ(a): = n2max{a_1,…,a_k} that allows us to distinguish three different regimes for this problem. We show that if Δ(a) < 0, then a star transposition Gray code for amultiset permutations does not exist. We also construct such Gray codes for the case Δ(a) > 0, assuming that they exist for the case Δ(a) = 0. For the case Δ(a) = 0 we present some partial positive results. Our proofs establish Hamiltonconnectedness or Hamiltonlaceability 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 Hamiltonlaceable.
BibTeX  Entry
@InProceedings{gregor_et_al:LIPIcs.STACS.2022.34,
author = {Gregor, Petr and M\"{u}tze, Torsten and Merino, Arturo},
title = {{Star Transposition Gray Codes for Multiset Permutations}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {34:134:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15844},
URN = {urn:nbn:de:0030drops158448},
doi = {10.4230/LIPIcs.STACS.2022.34},
annote = {Keywords: Gray code, permutation, combination, transposition, Hamilton cycle}
}
09.03.2022
Keywords: 

Gray code, permutation, combination, transposition, Hamilton cycle 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 