Gray Codes,Loopless Algorithm and Partitions |
| |
Authors: | Toufik Mansour Ghalib Nassar |
| |
Institution: | (1) Department of Mathematics, University of Haifa, 31905 Haifa, Israel |
| |
Abstract: | The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has
received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the
set of the partitions of n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of n]. In this paper, we give another combinatorial Gray code for the set of the partitions of n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set
of all partitions of n] which gives a constant time between successive partitions in the construction process.
|
| |
Keywords: | Gray codes Loopless algorithms Partitions Plane trees |
本文献已被 SpringerLink 等数据库收录! |
|