Document Open Access Logo

Trimming and Gluing Gray Codes

Authors Petr Gregor, Torsten Mütze

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.40.pdf
  • Filesize: 0.79 MB
  • 14 pages

Document Identifiers

Author Details

Petr Gregor
Torsten Mütze

Cite As Get BibTex

Petr Gregor and Torsten Mütze. Trimming and Gluing Gray Codes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.40

Abstract

We consider the algorithmic problem of generating each subset of [n]:={1,2,...,n} whose size is in some interval [k,l], 0 <= k <= l <= n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k=0 and l=n this is the classical problem of generating all 2^n subsets of [n] by element additions/removals, and for k=l this is the classical problem of generating all n over k subsets of [n] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n, k, and l, improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant time O(1) per generated set and space O(n). Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q_n induced by all levels [k,l]. We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q_(2k+1) induced by all levels [k-c,k+1+c], c in {0, 1, ... , k}, has a Hamilton cycle. We also prove an approximate version of this conjecture, showing that this graph has a cycle that visits a (1-o(1))-fraction of all vertices.

Subject Classification

Keywords
  • Gray code
  • subset
  • combination
  • loopless algorithm

Metrics

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

References

  1. URL: http://www.math.tu-berlin.de/~muetze.
  2. J. Bitner, G. Ehrlich, and E. Reingold. Efficient generation of the binary reflected Gray code and its applications. Comm. ACM, 19(9):517-521, 1976. Google Scholar
  3. M. Buck and D. Wiedemann. Gray codes with restricted density. Discrete Math., 48(2-3):163-171, 1984. URL: http://dx.doi.org/10.1016/0012-365X(84)90179-1.
  4. 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
  5. 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
  6. D. Duffus, H. Kierstead, and H. Snevily. An explicit 1-factorization in the middle of the Boolean lattice. J. Combin. Theory Ser. A, 65(2):334-342, 1994. URL: http://dx.doi.org/10.1016/0097-3165(94)90030-2.
  7. D. Duffus, B. Sands, and R. Woodrow. Lexicographic matchings cannot form Hamiltonian cycles. Order, 5(2):149-161, 1988. URL: http://dx.doi.org/10.1007/BF00337620.
  8. P. Eades, M. Hickey, and R. Read. Some Hamilton paths and a minimal change algorithm. J. Assoc. Comput. Mach., 31(1):19-29, 1984. URL: http://dx.doi.org/10.1145/2422.322413.
  9. 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: http://dx.doi.org/10.1016/0020-0190(84)90091-7.
  10. G. Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. Assoc. Comput. Mach., 20:500-513, 1973. Google Scholar
  11. M. El-Hashash and A. Hassan. On the Hamiltonicity of two subgraphs of the hypercube. In Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001), volume 148, pages 7-32, 2001. Google Scholar
  12. S. Felsner and W. Trotter. Colorings of diagrams of interval orders and α-sequences of sets. Discrete Math., 144(1-3):23-31, 1995. Combinatorics of ordered sets (Oberwolfach, 1991). URL: http://dx.doi.org/10.1016/0012-365X(94)00283-O.
  13. F. Gray. Pulse code communication. March 17, 1953 (filed Nov. 1947). U.S. Patent 2,632,058. Google Scholar
  14. P. Gregor and T. Mütze. Trimming and gluing Gray codes. arXiv:1607.08806, full version of this extended abstract, Jan 2017. URL: https://arxiv.org/abs/1607.08806.
  15. P. Gregor and R. Škrekovski. On generalized middle-level problem. Inform. Sci., 180(12):2448-2457, 2010. URL: http://dx.doi.org/10.1016/j.ins.2010.02.009.
  16. 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
  17. P. Horák, T. Kaiser, M. Rosenfeld, and Z. Ryjáček. The prism over the middle-levels graph is Hamiltonian. Order, 22(1):73-81, 2005. URL: http://dx.doi.org/10.1007/s11083-005-9008-7.
  18. T. Jenkyns and D. McCarthy. Generating all k-subsets of 1⋯ n with minimal changes. Ars Combin., 40:153-159, 1995. Google Scholar
  19. R. Johnson. Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A, 105(2):255-271, 2004. URL: http://dx.doi.org/10.1016/j.jcta.2003.11.004.
  20. H. Kierstead and W. Trotter. Explicit matchings in the middle levels of the Boolean lattice. Order, 5(2):163-171, 1988. URL: http://dx.doi.org/10.1007/BF00337621.
  21. D. Knuth. The Art of Computer Programming, Volume 4A. Addison-Wesley, 2011. Google Scholar
  22. S. Locke and R. Stong. Problem 10892: Spanning cycles in hypercubes. Amer. Math. Monthly, 110:440-441, 2003. Google Scholar
  23. T. Mütze. Proof of the middle levels conjecture. Proc. Lond. Math. Soc., 112(4):677-713, 2016. URL: http://dx.doi.org/10.1112/plms/pdw004.
  24. T. Mütze and J. Nummenpalo. Efficient computation of middle levels Gray codes. In N. Bansal and I. Finocchi, editors, Algorithms - ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 915-927. Springer Berlin Heidelberg, 2015. arXiv:1506.07898. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_76.
  25. T. Mütze and J. Nummenpalo. A constant-time algorithm for middle levels Gray codes. arXiv:1606.06172. An extended abstract has been accepted for presentation at SODA 2017, June 2016. Google Scholar
  26. T. Mütze and P. Su. Bipartite Kneser graphs are Hamiltonian. In J. Nešetril, O. Serra, and J. A. Telle, editors, Electronic Notes in Discrete Mathematics - Eurocomb 2015, volume 49, pages 259-267. Elsevier, 2015. arXiv:1503.09175. Accepted for publication in Combinatorica. Google Scholar
  27. T. Mütze and F. Weber. Construction of 2-factors in the middle layer of the discrete cube. J. Combin. Theory Ser. A, 119(8):1832-1855, 2012. URL: http://dx.doi.org/10.1016/j.jcta.2012.06.005.
  28. F. Ruskey. Adjacent interchange generation of combinations. J. Algorithms, 9(2):162-180, 1988. URL: http://dx.doi.org/10.1016/0196-6774(88)90036-3.
  29. C. Savage. Long cycles in the middle two levels of the Boolean lattice. Ars Combin., 35-A:97-108, 1993. Google Scholar
  30. C. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997. URL: http://dx.doi.org/10.1137/S0036144595295272.
  31. C. Savage and P. Winkler. Monotone Gray codes and the middle levels problem. J. Combin. Theory Ser. A, 70(2):230-248, 1995. URL: http://dx.doi.org/10.1016/0097-3165(95)90091-8.
  32. I. Shields, B. Shields, and C. Savage. An update on the middle levels problem. Discrete Math., 309(17):5271-5277, 2009. URL: http://dx.doi.org/10.1016/j.disc.2007.11.010.
  33. M. Shimada and K. Amano. A note on the middle levels conjecture. arXiv:0912.4564, Sep 2011. Google Scholar
  34. B. Stevens and A. Williams. The coolest way to generate binary strings. Theory Comput. Syst., 54(4):551-577, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9486-8.
  35. D. Tang and C. Liu. Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Computers, C-22:176-180, 1973. Google Scholar
  36. P. Winkler. Mathematical puzzles: a connoisseur’s collection. A K Peters, Ltd., Natick, MA, 2004. Google Scholar
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 About DROPS Imprint Privacy Contact