کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874760 1441206 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Necklaces and Lyndon words in colexicographic and binary reflected Gray code order
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Necklaces and Lyndon words in colexicographic and binary reflected Gray code order
چکیده انگلیسی
We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O(1)-time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volumes 46–47, September–November 2017, Pages 25-35
نویسندگان
, , ,