In this paper, we introduce a class of polyominoes, called deco polyominoes, in bijection with the set of permutations of the first k integers. We evaluate some typical parameters for this class of polyominoes and define a linear algorithm for randomly generating them. Moreover, we define the polyominoes corresponding to the directed animals on the hexagonal and triangular lattices and examine these polyominoes’ deco class. As far as deco polyominoes corresponding to animals on the hexagonal lattice are concerned, we find a bijection with a class of permutations. Finally, we give linear algorithms for randomly generating both hexagonal and triangular deco polyominoes.

"Deco" polyominoes, permutations and random generation / E. BARCUCCI; A. DEL LUNGO; R. PINZANI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 159:(1996), pp. 29-42. [10.1016/0304-3975(95)00199-9]

"Deco" polyominoes, permutations and random generation

BARCUCCI, ELENA;
1996

Abstract

In this paper, we introduce a class of polyominoes, called deco polyominoes, in bijection with the set of permutations of the first k integers. We evaluate some typical parameters for this class of polyominoes and define a linear algorithm for randomly generating them. Moreover, we define the polyominoes corresponding to the directed animals on the hexagonal and triangular lattices and examine these polyominoes’ deco class. As far as deco polyominoes corresponding to animals on the hexagonal lattice are concerned, we find a bijection with a class of permutations. Finally, we give linear algorithms for randomly generating both hexagonal and triangular deco polyominoes.
159
29
42
E. BARCUCCI; A. DEL LUNGO; R. PINZANI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/354163
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact