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: combinatorics, python

November 2008 December 2008 January 2009 May 2009 June 2009 July 2009

Subscribe to Posts [Atom]

## Post a Comment