𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generating convex polyominoes at random

✍ Scribed by Winfried Hochstättler; Martin Loebl; Christoph Moll

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
517 KB
Volume
153
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We give a new recursion formula for the number of convex polyominoes with fixed perimeter. From this we derive a bijection between an interval of natural numbers and the polyominoes of given perimeter. This provides a possibility to generate such polyominoes at random in polynomial time. Our method also applies for fixed area and even when fixing both, perimeter and area.

In the second part of the paper we present a simple linear time probabilistic algorithm which uniformly generates convex polyominoes of given perimeter with asymptotic probability 0.5.

📜 SIMILAR VOLUMES

The generating function of convex polyom
The generating function of convex polyominoes: The resolution of a q-differential system
✍ Mireille Bousquet-Mélou; Jean-Marc Fédou 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 825 KB

We give a 'beautiful' though complex -formula for the generating function Z of convex polyominoes, according to their area, width and height. Our method consists in solving a linear q-differential system of size three, which was derived two years ago by encoding convex polyominoes with the words of

Cataloging graphs by generating them uni
Cataloging graphs by generating them uniformly at random
✍ A. Kerber; R. Laue; R. Hager; W. Weber 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

## Abstract We describe an algorithm for cataloging graphs by generating them uniformly at random. The method used is based on a recent algorithm by Dixon and Wilf that generates orbit representatives uniformly at random. The approach is refined to graphs with prescribed numbers of edges and vertic