Instantly share code, notes, and snippets.

@wc /Oh.txt
Last active Oct 14, 2017

Embed
What would you like to do?
Computes the number of unique Eulerian paths on the octahedron modulo octahedral rotations
def find_eulerian_cycle(graph, path):
"""Find all Eulerian cycles starting with path."""
last = path[-1]
neighbors = graph[last]
if not neighbors:
if not any(graph) and path[0] == last:
yield tuple(path[:-1])
return
for v in neighbors:
new_graph = [x[:] for x in graph]
new_graph[last].remove(v)
new_graph[v].remove(last)
yield from find_eulerian_cycle(new_graph, path+[v])
# Mathematica equivalent: FindEulerianCycle[GraphData["OctahedralGraph"],All]
oct_graph = [[j for j in range(6) if i != j and i+j != 5] for i in range(6)]
edge = [0,1] # fixed cycle orientation and starting point
oct_graph[0].remove(1)
oct_graph[1].remove(0)
cycles = list(find_eulerian_cycle(oct_graph, edge))
print('Eulerian cycles:', len(cycles))
def O_h():
"""Build O_h, the octahedral group of order 48.
You can use Oh.txt to run this file without SymPy."""
from sympy.combinatorics.polyhedron import octahedron
from sympy.combinatorics.permutations import Permutation
from sympy.combinatorics.perm_groups import PermutationGroup
rot_generators = octahedron.pgroup.generators
ref_generator = Permutation([5,1,2,3,4,0]) # a reflection in array form
return PermutationGroup(rot_generators + [ref_generator])
def filter_dups(paths, sym_group):
"""Filter duplicates modulo the symmetry group."""
def rotations(path):
"""Generate all the octahedral rotations of path."""
for perm in sym_group.elements:
p = tuple(perm.array_form[v] for v in path) # apply permutation
for i in range(len(path)): # restore orientation
if p[i] == 0 and p[(i+1) % len(path)] == 1:
yield p[i:] + p[:i]
filtered = set()
for path in paths:
if not any(p in filtered for p in rotations(path)):
filtered.add(path)
return filtered
unique_cycles = filter_dups(cycles, sym_group=O_h())
print('Eulerian cycles modulo octahedral rotations:', len(unique_cycles))
[0, 1, 2, 3, 4, 5]
[0, 1, 4, 3, 2, 5]
[0, 2, 1, 4, 3, 5]
[0, 2, 3, 4, 1, 5]
[0, 3, 2, 1, 4, 5]
[0, 3, 4, 1, 2, 5]
[0, 4, 1, 2, 3, 5]
[0, 4, 3, 2, 1, 5]
[1, 0, 2, 5, 4, 3]
[1, 0, 4, 5, 2, 3]
[1, 2, 0, 4, 5, 3]
[1, 2, 5, 4, 0, 3]
[1, 4, 0, 2, 5, 3]
[1, 4, 5, 2, 0, 3]
[1, 5, 2, 0, 4, 3]
[1, 5, 4, 0, 2, 3]
[2, 0, 1, 5, 3, 4]
[2, 0, 3, 5, 1, 4]
[2, 1, 0, 3, 5, 4]
[2, 1, 5, 3, 0, 4]
[2, 3, 0, 1, 5, 4]
[2, 3, 5, 1, 0, 4]
[2, 5, 1, 0, 3, 4]
[2, 5, 3, 0, 1, 4]
[3, 0, 2, 5, 4, 1]
[3, 0, 4, 5, 2, 1]
[3, 2, 0, 4, 5, 1]
[3, 2, 5, 4, 0, 1]
[3, 4, 0, 2, 5, 1]
[3, 4, 5, 2, 0, 1]
[3, 5, 2, 0, 4, 1]
[3, 5, 4, 0, 2, 1]
[4, 0, 1, 5, 3, 2]
[4, 0, 3, 5, 1, 2]
[4, 1, 0, 3, 5, 2]
[4, 1, 5, 3, 0, 2]
[4, 3, 0, 1, 5, 2]
[4, 3, 5, 1, 0, 2]
[4, 5, 1, 0, 3, 2]
[4, 5, 3, 0, 1, 2]
[5, 1, 2, 3, 4, 0]
[5, 1, 4, 3, 2, 0]
[5, 2, 1, 4, 3, 0]
[5, 2, 3, 4, 1, 0]
[5, 3, 2, 1, 4, 0]
[5, 3, 4, 1, 2, 0]
[5, 4, 1, 2, 3, 0]
[5, 4, 3, 2, 1, 0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment