Instantly share code, notes, and snippets.

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

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]
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.