Computes the number of unique Eulerian paths on the octahedron modulo octahedral rotations

octahedral_cycles.py

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))

Oh.txt

[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]