# implementations of domino shuffling algorithm

Are there many implementations of the "domino shuffling" algorithm as found in 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".

-

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.)

-
what language is this written in? –  john mangual Jan 5 '12 at 23:38
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. –  john mangual Jan 5 '12 at 23:48
The applet is written in Java (and, being a decade old, no longer works for all platform-and-browser configurations). –  James Propp Jan 6 '12 at 15:46

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):

-
lol "shift or die" looks like you generate an ascii representation this way. Can you explain your notation "==", "--", "!|", "|!". –  john mangual Jan 5 '12 at 23:43
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. –  Benjamin Young Jan 6 '12 at 8:54

There is http://faculty.uml.edu/jpropp/tiling/www/applets/ but you should ask Jim Propp.

-