Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

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

share|improve this answer
    
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
add comment

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):Order 51 Aztec Diamond

share|improve this answer
    
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
1  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.