کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429059 687020 2011 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Loop-free Gray code algorithm for the e-restricted growth functions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Loop-free Gray code algorithm for the e-restricted growth functions
چکیده انگلیسی

The subject of Gray codes algorithms for the set partitions of {1,2,…,n}{1,2,…,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of Knuthʼs algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,…,n}{1,2,…,n}, Ruskey and Savage (1994) [9] generalized Ehrlichʼs results and give two Gray codes for the set of partitions of {1,2,…,n}{1,2,…,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques.In this paper, we introduce the set of e-restricted growth functions (a generalization of restricted growth functions) and extend the aforementioned results by giving a Gray code with distance one for this set; and as a particular case we obtain a new Gray code for set partitions in restricted growth function representation. Our Gray code satisfies some prefix properties and can be implemented by a loop-free generating algorithm using classical techniques; such algorithms can be used as a practical solution of some difficult problems. Finally, we give some enumerative results concerning the restricted growth functions of order d.


► We give a Gray code for the set of e-restricted growth functions.
► We obtain a new Gray code for the set partitions.
► We present a loop-free generating algorithm for our Gray code.
► We give some enumerative results concerning our restricted growth functions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 11, 15 May 2011, Pages 541–544
نویسندگان
, , ,