tc.py

# Example of Todd-Coxeter to compute S_3 from relations

idents = []
neighbors = []
to_visit = []
visited = set()

op_dir = [1, 0, 3, 2]

def find(c):
    c2 = idents[c]
    if c == c2:
        return c
    else:
        c2 = find(c2)
        idents[c] = c2
        return c2

def new():
    c = len(idents)
    idents.append(c)
    neighbors.append([None, None, None, None])
    to_visit.append(c)
    return c

def union(c1, c2):
    if c1 == None or c2 == None: return
    c1 = find(c1)
    c2 = find(c2)
    if c1 == c2:
        return
    if c1 in visited:
        visited.add(c2)
    idents[c1] = c2
    for d, (n1, n2) in enumerate(zip(neighbors[c1], neighbors[c2])):
        if n1 != None:
            if n2 == None:
                neighbors[c2][d] = n1
            else:
                union(n1, n2)

def follow(c, d, create=True):
    c = find(c)
    ns = neighbors[c]
    if ns[d] == None:
        if not create:
            return None
        ns[d] = new()
        neighbors[ns[d]][op_dir[d]] = c
    return find(ns[d])

def followp(c, ds):
    c = find(c)
    for d in reversed(ds):
        c = follow(c, d)
    return c

start = new()
to_visit.append(start)

while to_visit :
    c = find(to_visit.pop(0))
    if c in visited: continue
    visited.add(c)
    for d in range(0, 4):
        follow(c, d)

    # a^2=1
    union(followp(c, [0, 0]), c)
    # b^3=1
    union(followp(c, [2, 2, 2]), c)
    # baba=1
    union(followp(c, [2, 0, 2, 0]), c)

print "done"

cosets = list(set(find(c_) for c_ in visited))

a_perm = [cosets.index(follow(c, 0)) for i, c in enumerate(cosets)]
b_perm = [cosets.index(follow(c, 2)) for i, c in enumerate(cosets)]

print "a =", a_perm
print "b =", b_perm