Document Open Access Logo

Star Transposition Gray Codes for Multiset Permutations

Authors Petr Gregor, Torsten Mütze, Arturo Merino

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.34.pdf
  • Filesize: 2.29 MB
  • 14 pages

Document Identifiers

Author Details

Petr Gregor
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic
Torsten Mütze
  • Department of Computer Science, University of Warwick, Coventry, UK
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic
Arturo Merino
  • Department of Mathematics, TU Berlin, Germany

Funding

This work was supported by Czech Science Foundation grant GA 19-08554S, and by German Science Foundation grant 413902284.
  • Merino, Arturo: was also supported by ANID Becas Chile 2019-72200522.

Acknowledgements

We thank Jiří Fink for inspiring brain-storming sessions in the early phases of this research project, and we thank Aaron Williams for interesting discussions about star transposition Gray codes.

Cite AsGet BibTex

Petr Gregor, Torsten Mütze, and Arturo Merino. Star Transposition Gray Codes for Multiset Permutations. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.34

Abstract

Given integers k ≥ 2 and a_1,…,a_k ≥ 1, let a: = (a_1,…,a_k) and n: = a_1+⋯+a_k. An a-multiset 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 a-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 = ⋯ = 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): = n-2max{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 a-multiset 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 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Matchings and factors
Keywords
  • Gray code
  • permutation
  • combination
  • transposition
  • Hamilton cycle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. B. Alspach and Y. Qin. Hamilton-connected Cayley graphs on Hamiltonian groups. European J. Combin., 22(6):777-787, 2001. URL: https://doi.org/10.1006/eujc.2001.0456.
  2. T. Araki. Hyper Hamiltonian laceability of Cayley graphs generated by transpositions. Networks, 48(3):121-124, 2006. URL: https://doi.org/10.1002/net.20126.
  3. M. Buck and D. Wiedemann. Gray codes with restricted density. Discrete Math., 48(2-3):163-171, 1984. URL: https://doi.org/10.1016/0012-365X(84)90179-1.
  4. B. Cameron, J. Sawada, and A. Williams. A Hamilton cycle in the k-sided pancake network, 2021. URL: http://arxiv.org/abs/2103.09256.
  5. P. Chase. Combination generation and graylex ordering. Congr. Numer., 69:215-242, 1989. Eighteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1988). Google Scholar
  6. C. C. Chen and N. F. Quimpo. On strongly Hamiltonian abelian group graphs. In Combinatorial mathematics, VIII (Geelong, 1980), volume 884 of Lecture Notes in Math., pages 23-34. Springer, Berlin-New York, 1981. Google Scholar
  7. R. C. Compton and S. G. Williamson. Doubly adjacent Gray codes for the symmetric group. Linear and Multilinear Algebra, 35(3-4):237-293, 1993. URL: https://doi.org/10.1080/03081089308818261.
  8. P. F. Corbett. Rotator graphs: An efficient topology for point-to-point multiprocessor networks. IEEE Transactions on Parallel and Distributed Systems, 3:622-626, 1992. Google Scholar
  9. P. Diaconis and R. Graham. Magical mathematics. Princeton University Press, Princeton, NJ, 2012. The mathematical ideas that animate great magic tricks, With a foreword by Martin Gardner. Google Scholar
  10. P. Eades, M. Hickey, and R. C. Read. Some Hamilton paths and a minimal change algorithm. J. Assoc. Comput. Mach., 31(1):19-29, 1984. URL: https://doi.org/10.1145/2422.322413.
  11. P. Eades and B. McKay. An algorithm for generating subsets of fixed size with a strong minimal change property. Inform. Process. Lett., 19(3):131-133, 1984. URL: https://doi.org/10.1016/0020-0190(84)90091-7.
  12. P. Gregor, A. Merino, and T. Mütze. URL: http://arxiv.org/abs/2108.07465.
  13. P. Gregor, T. Mütze, and J. Nummenpalo. A short proof of the middle levels theorem. Discrete Analysis, 2018:8:12 pp., 2018. Google Scholar
  14. F. Harary and M. Lewinter. Hypercubes and other recursively defined Hamilton laceable graphs. Congr. Numer., 60:81-84, 1987. Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987). Google Scholar
  15. I. Havel. Semipaths in directed cubes. In Graphs and other combinatorial topics (Prague, 1982), volume 59 of Teubner-Texte Math., pages 101-108. Teubner, Leipzig, 1983. Google Scholar
  16. S.-Y. Hsieh, G.-H. Chen, and C.-W. Ho. Hamiltonian-laceability of star graphs. Networks, 36(4):225-232, 2000. URL: https://doi.org/10.1002/1097-0037(200012)36:4<225::AID-NET3>3.0.CO;2-G.
  17. T. Jenkyns and D. McCarthy. Generating all k-subsets of 1⋯ n with minimal changes. Ars Combin., 40:153-159, 1995. Google Scholar
  18. S. Johnson. Generation of permutations by adjacent transposition. Math. Comp., 17:282-285, 1963. Google Scholar
  19. D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011. Google Scholar
  20. V. L. Kompel'maher and V. A. Liskovec. Sequential generation of permutations by means of a transposition basis. Kibernetika (Kiev), 3:17-21, 1975. Google Scholar
  21. L. Lovász. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alberta, 1969). Gordon and Breach, New York, 1970. Google Scholar
  22. A. I. Merino, O. Mička, and T. Mütze. On a combinatorial generation problem of Knuth. In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 735-743. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.46.
  23. T. Mütze. Proof of the middle levels conjecture. Proc. Lond. Math. Soc., 112(4):677-713, 2016. URL: https://doi.org/10.1112/plms/pdw004.
  24. T. Mütze and J. Nummenpalo. A constant-time algorithm for middle levels Gray codes. Algorithmica, 82(5):1239-1258, 2020. URL: https://doi.org/10.1007/s00453-019-00640-2.
  25. A. Nijenhuis and H. Wilf. Combinatorial algorithms. Academic Press, New York-London, 1975. Computer Science and Applied Mathematics. Google Scholar
  26. F. Ruskey. Adjacent interchange generation of combinations. J. Algorithms, 9(2):162-180, 1988. URL: https://doi.org/10.1016/0196-6774(88)90036-3.
  27. F. Ruskey. Combinatorial Gray code. In M.-Y. Kao, editor, Encyclopedia of Algorithms, pages 342-347. Springer, 2016. Google Scholar
  28. F. Ruskey and C. D. Savage. Hamilton cycles that extend transposition matchings in Cayley graphs of S_n. SIAM J. Discrete Math., 6(1):152-166, 1993. URL: https://doi.org/10.1137/0406012.
  29. F. Ruskey and A. Williams. The coolest way to generate combinations. Discrete Math., 309(17):5305-5320, 2009. URL: https://doi.org/10.1016/j.disc.2007.11.048.
  30. C. D. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997. URL: https://doi.org/10.1137/S0036144595295272.
  31. J. Sawada and A. Williams. Greedy flipping of pancakes and burnt pancakes. Discrete Appl. Math., 210:61-74, 2016. URL: https://doi.org/10.1016/j.dam.2016.02.005.
  32. J. Sawada and A. Williams. Solving the sigma-tau problem. ACM Trans. Algorithms, 16(1):Art. 11, 17 pp., 2020. URL: https://doi.org/10.1145/3359589.
  33. X. S. Shen and A. Williams. A `hot potato' Gray code for permutations. Electronic Notes in Discrete Mathematics, 44:89-94, 2013. URL: https://doi.org/10.1016/j.endm.2013.10.014.
  34. X. S. Shen and A. Williams. A k-ary middle levels conjecture. In Proceedings of the 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021. Google Scholar
  35. G. J. Simmons. Almost all n-dimensional rectangular lattices are Hamilton-laceable. In Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congress. Numer., XXI, pages 649-661. Utilitas Math., Winnipeg, Man., 1978. Google Scholar
  36. P. J. Slater. Generating all permutations by graphical transpositions. Ars Combin., 5:219-225, 1978. Google Scholar
  37. G. Stachowiak. Hamilton paths in graphs of linear extensions for unions of posets. SIAM J. Discrete Math., 5(2):199-206, 1992. URL: https://doi.org/10.1137/0405016.
  38. D. Tang and C. Liu. Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Computers, C-22:176-180, 1973. Google Scholar
  39. M. Tchuente. Generation of permutations by graphical exchanges. Ars Combin., 14:115-122, 1982. Google Scholar
  40. H. F. Trotter. Algorithm 115: Perm. Commun. ACM, 5(8):434-435, 1962. URL: https://doi.org/10.1145/368637.368660.
  41. A. Williams. The greedy Gray code algorithm. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings, pages 525-536, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_46.
  42. P. Winkler. Mathematical puzzles: a connoisseur’s collection. A K Peters, Ltd., Natick, MA, 2004. Google Scholar
  43. S. Zaks. A new algorithm for generation of permutations. BIT, 24(2):196-204, 1984. URL: https://doi.org/10.1007/BF01937486.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact