کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431764 688624 2006 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A loop-free two-close Gray-code algorithm for listing k-ary Dyck words
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A loop-free two-close Gray-code algorithm for listing k-ary Dyck words
چکیده انگلیسی

P. Chase and F. Ruskey each published a Gray code for length n binary strings with m occurrences of 1, coding m-combinations of n   objects, which is two-close—that is, in passing from one binary string to its successor a single 1 exchanges positions with a 0 which is either adjacent to the 1 or separated from it by a single 0. If we impose the restriction that any suffix of a string contains at least k−1k−1 times as many 0's as 1's, we obtain k-suffixes: suffixes of k  -ary Dyck words. Combinations are retrieved as special case by setting k=1k=1 and k  -ary Dyck words are retrieved as a special case by imposing the additional condition that the entire string has exactly k−1k−1 times as many 0's as 1's. We generalize Ruskey's Gray code to the first two-close Gray code for k  -suffixes and we provide a loop-free implementation for k⩾2k⩾2. For k=1k=1 we use a simplified version of Chase's loop-free algorithm for generating his two-close Gray code for combinations. These results are optimal in the sense that there does not always exist a Gray code, either for combinations or Dyck words, in which the 1 and the 0 that exchange positions are adjacent.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 4, Issue 4, December 2006, Pages 633–648
نویسندگان
, ,