کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649187 | 1342445 | 2009 | 14 صفحه PDF | دانلود رایگان |
We introduce the problem of polyomino Gray codes, which is the listing of all members of certain classes of polyominoes such that successive polyominoes differ by some well-defined closeness condition (e.g., the movement of one cell). We discuss various closeness conditions and provide several Gray codes for the class of column-convex polyominoes with a fixed number of cells in each column. For one of our closeness conditions, a natural new class of distributive lattice arises: the partial order is defined on the set of mm-tuples [S1]×[S2]×⋯×[Sm][S1]×[S2]×⋯×[Sm], where each Si>1Si>1 and [Si]={0,1,…,Si−1}[Si]={0,1,…,Si−1}, and the cover relations are (p1,p2,…,pm)≺(p1+1,p2,…,pm)(p1,p2,…,pm)≺(p1+1,p2,…,pm) and (p1,p2,…,pj,pj+1,…,pm)≺(p1,p2,…,pj−1,pj+1+1,…,pm)(p1,p2,…,pj,pj+1,…,pm)≺(p1,p2,…,pj−1,pj+1+1,…,pm). We also discuss some properties of this lattice.
Journal: Discrete Mathematics - Volume 309, Issue 17, 6 September 2009, Pages 5284–5297