# implementing Propp-Wilson's Coupling From the Past on Lozenge Tilings of a Hexagon

I'm trying to write a program (with javascript or python) that samples a random lozenge tiling of a hexagon with Propp - Wilson's coupling from the past algorithm. I'm quite clear of the framework of the algorithm, but I don't know which is the most efficient way to encode a tiling, or whether different encoding methods would result in non-uniform samplers.

I have at least 3 possible way to encode a lozenge tiling of a hexagon:

1. View it as a plane partition, i.e. piling cubes in a 3D room. This is quite intuitive, but not easy to implement the add - remove step.

2. View it as a non-intersecting path system. Each path is further represented by a 0-1 array.

3. encode it as a interlacing array (which I have not understand it yet). But I have seen at least 3 people that mentioned this approach. For example here

So my question is: which is the best way to encode a tiling, or can anyone explain the 3rd approach?

Actually, there is a slightly different representation that might be better and has been popular in the past. In the case of regular partitions, it turns the partition 45 degrees, so that the gravity pulling boxes into the corner is now the $y$ axis. The $x$-axis parameterizes diagonal stacks of boxes, touching corner to corner. We record an array index by $x$ of the heights of these stacks. This restores the symmetry of the axes. Similarly, we can represent a (boxed) plane partition as a hexagonal grid of heights, where height is $x+y+z$.
• There is really only one partial order. But there are many Gibbs chains because every representation gives you a different sense of "local structure." Maybe there is a universal one, where you choose one of the $n^3$ boxes and forget whether it is present. But it is more efficient to group together boxes into $O(n^2)$ sets and forget about all of them at once. In particular, if you use either representation as an array of numbers, you can erase one of those numbers. But for CFTP it is important to make the choice of a replacement number be "the same" for all configurations, compatible w/order. Commented Jan 27, 2017 at 15:07