Set of enumerators of multiple types of polyominoes (snake, tree, etc.)
Project description
The files of this repository allows one to enumerate polyominoes based on Jensen’s algorithm. The code is written in Python, but it has been optimized using Cython.
Dependencies
Python module dependencies
Roadmap
Update the docstring in polyenum package (enumerators, data_structures modules).
Enhance –north-snake option implementation. The criterion for exluding invalid north snake candidate can be enhanced using the fact that for any row of a north snake the pattern x...0...x cannot be found. Since the algorithm builds polyominoes column after column, it would be a good idea to make all of the “left snakes” and rotate the results.
Creates a test suite.
Implements Knuth’s algorithm for the minimum connectivity problem (see comment in source code). This will improve significantly the speed when enumerating polyominoes.
Takes into account symmetry to improve speed of algorithm. It will also allow to generate free/fixed/one-sided polyominoes. Currently, only fixed polyominoes are generated.
Add other types of installers (MacPorts, Homebrew, Windows, Debian package, ArchLinux).
Add a script for extracting statistics and classifying.
Add a script for drawing.
Improve speed for enumerating partially directed snakes (it uses a Python boolean list instead of a bool*). Moreover, the enumeration columnwise could discard more configurations than by looking only at the pillars.
Howto use
The script polyenum is used to call the enumeration code. You can ./scripts/polyenum --help for help.
From git repository
In order for the script to run properly, the Cython library has to be compiled. It’s done by doing:
$ ./configure $ make
and then, polyenum will be available under ./scripts directory.
Example
Enumerating all polyominoes of given area
Let the area of the polyominoes be 4. Finding all the polyominoes (not inscribed in a particular rectangle) of area 4 is done as follows:
$ ./polyenum -a 4 --fixed Fixed polyomino enumeration. XXXX X X X X XX XX X-- XXX XX -X -X XXX X-- XX X- X- -X- XXX -X XX -X -XX XX- -X XX X- --X XXX -X -X XX XX- -XX X- XX -X XXX -X- X- XX X- XXX --X X- X- XX Time elapsed: 0.000782012939453125 seconds Number of polyominoes: 19
More examples can be found reading polyenum’s man page (man ./doc/polyenum.1).
Installing
From PyPi dist release
Simply do:
python2.7 setup.py install
From git repository
The script can be installed on your system. This is useful since it provides bash tab completion capability for the script. To install, simply do:
$ ./configure $ make # make install
NOTE: Most of the installation process is done by python. On some platforms, python may install scripts under a directory which is not in your $PATH bash environnement variable.
Bash Completion
In order to install bash completion, do the following
$ BASH_COMPLETION_DIR=$p ./configure $ make # make install
where $p is the path to the directory where bash-completion scripts are installed on your system.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for polyenum-0.1_1-py2.7-linux-x86_64.egg
Algorithm | Hash digest | |
---|---|---|
SHA256 | e1d275b43608ebd7e147f0d77f71f0c3d8b3bbbc46840a6ad3323a4826748c7b |
|
MD5 | d5ae3a974fde3e903c0599242cacf980 |
|
BLAKE2b-256 | febd361052ad53495c3212e0e4c899603191467f4a63b4eebf501614e3976e6e |
Hashes for polyenum-0.1-1.linux-x86_64.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 77f4be0e56e883381fd4ebc1f3393131f775920447451acf2435fbb1a9cf254c |
|
MD5 | d30023aaeb4f20f4bfc4b4973d8a4577 |
|
BLAKE2b-256 | 4935ed82c4dcb571d5a3f47a7f1621d9281c43e5f42aa901de83dc0406ca6bca |