Skip to main content
SpringerLink
Log in

A Constant-Time Algorithm for Middle Levels Gray Codes

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

For any integer \(n\ge 1\), a middle levels Gray code is a cyclic listing of all n-element and \((n+1)\)-element subsets of \(\{1,2,\ldots ,2n+1\}\) such that any two consecutive sets differ in adding or removing a single element. The question whether such a Gray code exists for any \(n\ge 1\) has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. Proc. London Math. Soc., 112(4):677–713, 2016]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. ACM Trans. Algorithms, 14(2):29 pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time \({{\mathcal {O}}}(n)\) on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time \({{\mathcal {O}}}(1)\) on average, and the required space is \({{\mathcal {O}}}(n)\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Mütze, T., Nummenpalo, J.: A constant-time algorithm for middle levels Gray codes. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16–19, pp. 2238–2253 (2017)

  2. Savage, C.D.: A survey of combinatorial Gray codes. SIAM Rev. 39(4), 605–629 (1997)

    MathSciNet  MATH  Google Scholar 

  3. Knuth, D.E.: The Art of Computer Programming, Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ (2011)

  4. Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms. Academic Press, New York-London (1975). Computer Science and Applied Mathematics

  5. Wilf, H.S.: Combinatorial algorithms: an update, volume 55 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1989)

  6. Johnson, S.M.: Generation of permutations by adjacent transposition. Math. Comput. 17, 282–285 (1963)

    MathSciNet  MATH  Google Scholar 

  7. Trotter, H.: Algorithm 115: Perm. Commun. ACM 5(8), 434–435 (1962)

    Google Scholar 

  8. Dershowitz, N.: A simplified loop-free algorithm for generating permutations. Nordisk Tidskr. Informationsbehandling (BIT) 15(2), 158–164 (1975)

    MathSciNet  MATH  Google Scholar 

  9. Sedgewick, R.: Permutation generation methods. Comput. Surv. 9(2), 137–164 (1977)

    MathSciNet  MATH  Google Scholar 

  10. Gray, F.: Pulse code communication (1953). March 17 (filed Nov. 1947). U.S. Patent 2,632,058

  11. Ehrlich, G.: Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. Assoc. Comput. Mach. 20, 500–513 (1973)

    MathSciNet  MATH  Google Scholar 

  12. Bitner, J., Ehrlich, G., Reingold, E.: Efficient generation of the binary reflected Gray code and its applications. Commun. ACM 19(9), 517–521 (1976)

    MathSciNet  MATH  Google Scholar 

  13. Eades, P., Hickey, M., Read, R.C.: Some Hamilton paths and a minimal change algorithm. J. Assoc. Comput. Mach. 31(1), 19–29 (1984)

    MathSciNet  MATH  Google Scholar 

  14. Eades, P., McKay, B.: An algorithm for generating subsets of fixed size with a strong minimal change property. Inform. Process. Lett. 19(3), 131–133 (1984)

    MathSciNet  MATH  Google Scholar 

  15. Ruskey, F.: Adjacent interchange generation of combinations. J. Algorithms 9(2), 162–180 (1988)

    MathSciNet  MATH  Google Scholar 

  16. Zerling, D.: Generating binary trees using rotations. J. Assoc. Comput. Mach. 32(3), 694–701 (1985)

    MathSciNet  MATH  Google Scholar 

  17. Lucas, J.M.: The rotation graph of binary trees is Hamiltonian. J. Algorithms 8(4), 503–535 (1987)

    MathSciNet  MATH  Google Scholar 

  18. Lucas, J.M., Roelants van Baronaigien, D., Ruskey, F.: On rotations and the generation of binary trees. J. Algorithms 15(3), 343–366 (1993)

    MathSciNet  MATH  Google Scholar 

  19. Cummins, R.L.: Hamilton circuits in tree graphs. IEEE Trans. Circuit Theory CT-13:82–90 (1966)

    MathSciNet  Google Scholar 

  20. Kamae, T.: The existence of a Hamilton circuit in a tree graph. IEEE Trans. Circuit Theory CT-14:279–283 (1967)

    MathSciNet  Google Scholar 

  21. Holzmann, C.A., Harary, F.: On the tree graph of a matroid. SIAM J. Appl. Math. 22, 187–193 (1972)

    MathSciNet  MATH  Google Scholar 

  22. Havel, I.: Semipaths in directed cubes. In: Graphs and Other Combinatorial Topics (Prague, 1982), volume 59 of Teubner-Texte Math., pages 101–108. Teubner, Leipzig (1983)

  23. Buck, M., Wiedemann, D.: Gray codes with restricted density. Discrete Math. 48(2–3), 163–171 (1984)

    MathSciNet  MATH  Google Scholar 

  24. Kierstead, H.A., Trotter, W.T.: Explicit matchings in the middle levels of the Boolean lattice. Order 5(2), 163–171 (1988)

    MathSciNet  MATH  Google Scholar 

  25. Winkler, P.: Mathematical Puzzles: A Connoisseur’s Collection. A K Peters Ltd., Natick (2004)

    MATH  Google Scholar 

  26. Diaconis, P., Graham, R.: Magical Mathematics. Princeton University Press, Princeton, NJ (2012). The mathematical ideas that animate great magic tricks, With a foreword by Martin Gardner

  27. Gowers, W.T.: Probabilistic combinatorics and the recent work of Peter Keevash. Bull. Am. Math. Soc. (N.S.) 54(1), 107–116 (2017)

    MathSciNet  MATH  Google Scholar 

  28. Savage, C.D.: Long cycles in the middle two levels of the Boolean lattice. Ars Combin. 35–A, 97–108 (1993)

    MathSciNet  MATH  Google Scholar 

  29. Felsner, S., Trotter, W.T.: Colorings of diagrams of interval orders and \(\alpha \)-sequences of sets. Discrete Math. 144(1–3), 23–31 (1995). Combinatorics of ordered sets (Oberwolfach, 1991)

    MathSciNet  MATH  Google Scholar 

  30. Savage, C.D., Winkler, P.: Monotone Gray codes and the middle levels problem. J. Combin. Theory Ser. A 70(2), 230–248 (1995)

    MathSciNet  MATH  Google Scholar 

  31. Johnson, J.R.: Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A 105(2), 255–271 (2004)

    MathSciNet  MATH  Google Scholar 

  32. Duffus, D., Sands, B., Woodrow, R.: Lexicographic matchings cannot form Hamiltonian cycles. Order 5(2), 149–161 (1988)

    MathSciNet  MATH  Google Scholar 

  33. Duffus, D.A., Kierstead, H.A., Snevily, H.S.: An explicit \(1\)-factorization in the middle of the Boolean lattice. J. Combin. Theory Ser. A 65(2), 334–342 (1994)

    MathSciNet  MATH  Google Scholar 

  34. Horák, P., Kaiser, T., Rosenfeld, M., Ryjáček, Z.: The prism over the middle-levels graph is Hamiltonian. Order 22(1), 73–81 (2005)

    MathSciNet  MATH  Google Scholar 

  35. Gregor, P., Škrekovski, R.: On generalized middle-level problem. Inform. Sci. 180(12), 2448–2457 (2010)

    MathSciNet  MATH  Google Scholar 

  36. Mütze, T., Weber, F.: Construction of 2-factors in the middle layer of the discrete cube. J. Combin. Theory Ser. A 119(8), 1832–1855 (2012)

    MathSciNet  MATH  Google Scholar 

  37. Shields, I., Shields, B., Savage, C.D.: An update on the middle levels problem. Discrete Math. 309(17), 5271–5277 (2009)

    MathSciNet  MATH  Google Scholar 

  38. Shimada, M., Amano, K.: A note on the middle levels conjecture. arXiv:0912.4564 (September 2011)

  39. Mütze, T.: Proof of the middle levels conjecture. Proc. Lond. Math. Soc. 112(4), 677–713 (2016)

    MathSciNet  MATH  Google Scholar 

  40. Gregor, P., Mütze, T., Nummenpalo, J.: A short proof of the middle levels theorem. Discrete Anal. 8, 12 (2018)

    MathSciNet  MATH  Google Scholar 

  41. Mütze, T., Nummenpalo, J.: Efficient computation of middle levels Gray codes. ACM Trans. Algorithms (TALG), 14(2):29 pp., 2018. An extended abstract appeared in the Proceedings of the European Symposium on Algorithms (ESA 2015)

    MathSciNet  MATH  Google Scholar 

  42. The Combinatorial Object Server. http://combos.org

  43. Simpson, J.E.: Hamiltonian bipartite graphs. In: Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Vol. 85, pp. 97–110 (1991)

  44. Hurlbert, G.: The antipodal layers problem. Discrete Math. 128(1–3), 237–245 (1994)

    MathSciNet  MATH  Google Scholar 

  45. Chen, Y.: Kneser graphs are Hamiltonian for \(n\ge 3k\). J. Combin. Theory Ser. B 80(1), 69–79 (2000)

    MathSciNet  MATH  Google Scholar 

  46. Chen, Y.: Triangle-free Hamiltonian Kneser graphs. J. Combin. Theory Ser. B 89(1), 1–16 (2003)

    MathSciNet  MATH  Google Scholar 

  47. Mütze, T., Su, P.: Bipartite Kneser graphs are Hamiltonian. Combinatorica 37(6), 1207–1219 (2017)

    MathSciNet  MATH  Google Scholar 

  48. Gregor, P., Mütze, T.: Trimming and gluing Gray codes. Theoret. Comput. Sci. 714, 74–95 (2018)

    MathSciNet  MATH  Google Scholar 

  49. Herter, F., Rote, G.: Loopless Gray code enumeration and the tower of Bucharest. In: 8th International Conference on Fun with Algorithms, FUN 2016, June 8–10, 2016, La Maddalena, Italy, pages 19:1–19:19 (2016)

  50. Mütze, T., Standke, C., Wiechert, V.: A minimum-change version of the Chung-Feller theorem for Dyck paths. Eur. J. Combin. 69, 260–275 (2018)

    MathSciNet  MATH  Google Scholar 

  51. Booth, K.S.: Lexicographically least circular substrings. Inform. Process. Lett. 10(4–5), 240–242 (1980)

    MathSciNet  MATH  Google Scholar 

  52. Stanley, R.P.: Catalan Numbers. Cambridge University Press, New York (2015)

    MATH  Google Scholar 

  53. Skiena, S.: The Algorithm Design Manual, 2nd edn. Springer, New York (2008)

    MATH  Google Scholar 

Download references

Acknowledgements

We thank the anonymous referee for the careful reading and many helpful comments that considerably improved the readability of this manuscript.

Author information

Authors and Affiliations

  1. Institut für Mathematik, TU Berlin, 10623, Berlin, Germany

    Torsten Mütze

  2. Department of Computer Science, ETH Zürich, 8092, Zürich, Switzerland

    Jerri Nummenpalo

Authors
  1. Torsten Mütze
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jerri Nummenpalo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Torsten Mütze.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An extended abstract of this paper appeared in the Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 [1]. Torsten Mütze is also affiliated with Charles University, Faculty of Mathematics and Physics, and was supported by Czech Science Foundation Grant GA 19-08554S, and by German Science Foundation Grant 413902284.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mütze, T., Nummenpalo, J. A Constant-Time Algorithm for Middle Levels Gray Codes. Algorithmica 82, 1239–1258 (2020). https://doi.org/10.1007/s00453-019-00640-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-019-00640-2

Keywords

Search

Navigation