Question

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

Answer 1

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

Answer 2

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

Answer 3

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