2016/06/20 by Mütze, Torsten, Nummenpalo, Jerri
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1606.06172
For any integer n≥ 1 a middle levels Gray code is a cyclic listing of all n-element and (n+1)-element subsets of \1,2,…,2n+1\ such that any two consecutive subsets differ in adding or removing a single element. The question whether such a Gray code exists for any n≥ 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. To appear in ACM Transactions on Algorithms, 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time 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 O(1) on average, and the required space is O(n).