Are there many implementations of the "domino shuffling" algorithm as found in William Jockusch, James Propp amd Peter Shor's Random Domino Tilings and the Arctic Circle Theorem math.CO/9801068? This topic may be out of fashion now but I wonder if any source code is circulating. I'm doing it myself, but I always have this fear of "reinventing the wheel".
$\begingroup$
$\endgroup$
0
asked Sep 29, 2010 at 7:47
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
I use http://halcanary.org/mathapplets/toadshuffle/toadshuffle-v1.3/ by Hal Canary. (The reference Aaron Meyerowitz gave is for generating random tilings via coupling-from-the-past, which is quite different from domino-shuffling.)
answered Jan 4, 2012 at 5:03
-
-
$\begingroup$ I think if all I wanted to do is draw a nice picture, I may not even need CFTP, I would just start from uniform and swap. For large tilings, that gets slow (if I remember). Domino shuffling is very fast, but it only work in particular cirumstances... I still hve trouble implementing it... really should be on github or something. $\endgroup$ Jan 5, 2012 at 23:48
-
$\begingroup$ The applet is written in Java (and, being a decade old, no longer works for all platform-and-browser configurations). $\endgroup$ Jan 6, 2012 at 15:46
-
$\begingroup$ I mean to translate that code into HTML5/canvas, but have not found the time yet. $\endgroup$ Oct 21, 2018 at 15:21
$\begingroup$
$\endgroup$
2
Here is one which produces ASCII art aztec diamond tilings. It's written in perl. As I recall, I wrote it as fast as possible, without making any attempt to do it efficiently, because I needed to make some pictures really quickly.
#!/usr/bin/perl -w
use strict;
#=================================================================
sub delete_odd_blocks($) {
my $diamond = shift;
for my $r (0..scalar @$diamond - 2) {
my $c = index($$diamond[$r], "--" );
while($c != -1) {
if(substr($$diamond[$r+1], $c, 2) eq "==") {
substr($$diamond[$r], $c, 2) = "BB";
substr($$diamond[$r+1], $c, 2) = "BB";
}
$c = index($$diamond[$r], "--", $c + 2);
}
$c = index($$diamond[$r], "!|" );
while($c != -1) {
if(substr($$diamond[$r+1], $c, 2) eq "!|") {
substr($$diamond[$r], $c, 2) = "BB";
substr($$diamond[$r+1], $c, 2) = "BB";
}
$c = index($$diamond[$r], "!|", $c + 2);
}
}
}
#=================================================================
sub slide($) {
my $diamond = shift;
my $N = scalar @$diamond; # $N rows in the diamond
die "$N is an odd number" if($N % 2);
my (@output);
for my $r (0..$N/2) {
my $row = " "x$r . "A" x($N - 2*$r+2) . " "x$r;
push @output, $row;
unshift @output, $row;
}
push @$diamond, " "x $N;
for my $r (0..scalar @$diamond - 1) {
my $c = index($$diamond[$r], "|" );
while($c != -1) {
if(substr($$diamond[$r+1], $c, 1) eq "|") {
substr($output[$r+1], $c, 1) = "|";
substr($output[$r+2], $c, 1) = "|";
}
$c = index($$diamond[$r], "|", $c + 1);
}
$c = index($$diamond[$r], "!" );
while($c != -1) {
if(substr($$diamond[$r+1], $c, 1) eq "!") {
substr($output[$r+1], $c+2, 1) = "!";
substr($output[$r+2], $c+2, 1) = "!";
}
$c = index($$diamond[$r], "!", $c + 1);
}
$c = index($$diamond[$r], "--" );
while($c != -1) {
substr($output[$r+2], $c+1, 2) = "--";
$c = index($$diamond[$r], "--", $c + 2);
}
$c = index($$diamond[$r], "==" );
while($c != -1) {
substr($output[$r], $c+1, 2) = "==";
$c = index($$diamond[$r], "==", $c + 2);
}
}
pop @$diamond;
\@output;
}
#=================================================================
sub fill_even_blocks($) {
my $diamond = shift;
for my $r (0..scalar @$diamond - 2) {
my $c = index($$diamond[$r], "AA" );
while($c != -1) {
if(substr($$diamond[$r+1], $c, 2) eq "AA") {
if(rand() < 0.5) {
substr($$diamond[$r],$c,2) = "==";
substr($$diamond[$r+1],$c,2)= "--";
} else {
substr($$diamond[$r],$c,2) = "|!";
substr($$diamond[$r+1],$c,2)= "|!";
}
}
$c = index($$diamond[$r], "AA", $c + 2);
}
}
}
my $dimers;
if(rand() < 0.5) {
$dimers = ["|!", "|!"];
} else {
$dimers = ["==", "--"];
}
my $n = shift or die "Tell me the order of the diamond please\n";
for(1..$n-1) {
delete_odd_blocks($dimers);
$dimers = slide($dimers);
fill_even_blocks($dimers);
}
for (@$dimers) {
print "$_\n"
}
Here is a sample of the output (the outcome of running "perl shuffle 5" on the command line, if you called this script shuffle):
==
====
|!|!==
||!|!--!
|||!|!==!!
|||!|!!|!!
||--!!|!
||!!--
|!--
--
The domino shuffling algorithm has four types of dominoes: northbound, southbound, eastbound and westbound. I use "==", "--", for the northbound, southbound ones; two | symbols for the westbound ones and two ! for the eastbound ones.
This script, as I recall, was the first link in a tool chain which produced the following image of the height function of an Aztec Diamond (this link will eventually go stale, but it should be good for a year or two anyway):
-
$\begingroup$ lol "shift or die" looks like you generate an ascii representation this way. Can you explain your notation "==", "--", "!|", "|!". $\endgroup$ Jan 5, 2012 at 23:43
-
1$\begingroup$ Edited to include sample output and descriptions of how I represent the dominoes. The order $n$ tiling is a $2n$-dimensional array of length $2n$ strings, made of the five characters " =-!|". "==", "--", "!|", "|!" are all portions of the tiling itself. In particular, "==", "--" are N and S dominoes; "!|" and "|!" are the top half of an odd block and an even block, respectively. "shift or die" is a perl idiom for reading an argument from the command line and raising an error if it's not there. $\endgroup$ Jan 6, 2012 at 8:54
$\begingroup$
$\endgroup$
There is http://faculty.uml.edu/jpropp/tiling/www/applets/ but you should ask Jim Propp.
answered Sep 29, 2010 at 8:14