Discrete Mathematics & Theoretical Computer Science,Vol 9, No 2 (2007)

摘要

At the 4th Conference on Combinatorics on Words,Christophe Reutenauer posed the question of whether the dual reflected orderyields a Gray code on the Lyndon family.In this paper we give a positive answer.More precisely, we present an O(1)-average-time algorithm for generating length nbinary pre-necklaces, necklaces and Lyndon words in Gray code order.