Personal Web Page

Sunday, January 4, 2009

 

Domino counting problem

My brother is writing a combinatorics paper about playing with dominoes. Pure mathematics is a lot of fun that way, but with more Hamiltonian paths of graphs embedded on a torus. Here is a Python script I wrote for him last night to solve a counting problem.


#!/usr/bin/env python
# Author: Jared Brothers
# Find the orderings of a set of dominoes such that
# adjacent dominoes share a number and the other two
# numbers differ by one.

def search(start):
""" Depth first search, generating all solutions. """
fringe = [start]
while fringe:
s = fringe.pop()
if s.check():
yield s
fringe.extend(s.successors())

class state():
""" A state in the search space. """
def __init__(self, d, r):
""" The ordered dominoes are in done (list),
and the unordered dominoes are in rest (set). """
self.done = d
self.rest = r

def __str__(self):
return str(self.done)

def check(self):
""" Is this a solution? """
return not self.rest

def successors(self):
""" The states you can get to by moving a domino from rest to done. """
if self.done:
# Try only dominoes adjacent to the previous one,
a,b = self.done[-1]
a1 = (a + 1) % n
a2 = (a - 1) % n
b1 = (b + 1) % n
b2 = (b - 1) % n
adjs = set([(a,b1), (b1,a), (a,b2), (b2,a), (b,a1), (a1,b), (b,a2), (a2,b)])
for x in self.rest.intersection(adjs):
d = self.done[:]
d.append(x)
r = self.rest.copy()
r.discard(x)
yield state(d, r)
else:
# or all the rest if nothing has been done yet.
for x in sorted(self.rest):
d = [x]
r = self.rest.copy()
r.discard(x)
yield state(d, r)

if __name__ == '__main__':
n = 7 # The number of numbers. The number of dominoes is sum(range(n + 1)).
start = state([], set((a, b) for a in range(n) for b in range(a + 1)))
for s in search(start):
print(s)

Labels: ,


My Photo
Name: Jared Brothers
Location: New York, NY, United States

Links

Archives

November 2008   December 2008   January 2009   June 2009   July 2009  

This page is powered by Blogger. Isn't yours?

Subscribe to Posts [Atom]