implementations of domino shuffling algorithm

2010-09-29T07:47:42Z

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 by Aaron Meyerowitz for implementations of domino shuffling algorithm

2010-09-29T08:14:47Z

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

Answer by James Propp for implementations of domino shuffling algorithm

2012-01-04T05:03:16Z

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 by Benjamin Young for implementations of domino shuffling algorithm

2012-01-04T21:48:54Z

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

implementations of domino shuffling algorithm - MathOverflow

implementations of domino shuffling algorithm

Answer by Aaron Meyerowitz for implementations of domino shuffling algorithm

Answer by James Propp for implementations of domino shuffling algorithm

Answer by Benjamin Young for implementations of domino shuffling algorithm