Algorithm for factoring elements of permutation groups?

Question

You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). There are several algorithms for solving Rubik's cubes. Are there any algorithms for the general problem of factoring permutations?

• Simon: Do you seek a set of generators for the symmetric group $S_n$ on $n$ symbols ? Or an algorithm for finding a set of generators for a given subgroup of $S_n$ ? If the latter, then how will that subgroup be input to your algorithm ? I mean how will the group be represented ? Simply as it's set of elements ?
• Display Name: @Simon I have a set of generators for $S_n$ and would like to decompose any given group element into a product of generators and their inverses. The inputs to the algorithm are a set of generator permutations $g_1, g_2, \cdots, g_n$ and a target permutation $h,ドル and what is desired is a product like $h = g_2 g_1^{-1}g_{50}$. That's why I say it's kind of like factoring.
• Simon: That is interesting. Since an arbitrary permutation can be expressed as a product of disjoint cycles, perhaps you should first try to make an algorithm for expressing a single arbitrary cycle as a word in your generators ? You already have a set of generators in mind, however I seem to remember that the cyclic permutation $(1, ..., n)$ and the 2-element permutation $(1, 2)$ together form a set of generators for $S_n$. Perhaps it would be relatively "easy" to express an arbitrary cycle as a word in these two generators ?
• Display Name: Since bubble sort only exchanges adjacent pairs, any execution of the bubble sort algorithm can be expressed as a product of cyclic permutations and the $(2,1)$ permutation. I am not sure how to write the result in terms of an arbitrary generator set, though.
• Simon: What set of generators of $S_n$ are you planning to use ? I suppose that the design of the algorithm will depend on this choice.

Answer 1

Let $S$ be a set of generators in $S_n$ such that $S$ is closed under inverses, and let $h \in S_n$. The goal is to express $h$ as a product of elements of $S$. A graph-theoretic approach to solve this problem is to construct the Cayley digraph of $S_n$ with respect to generating set $S$, denoted $G = Cay(S_n,S)$, which is defined to be the graph with vertex set $S_n$ and arc set $\{ (g,sg): g \in S_n, s \in S\}$. One can also construct an arc-labeled graph where arc $(g,sg)$ has label $s$.

Thus, if $b = (1,2,3,4,5)$, then there is an arc in the Cayley graph $G$ from the identity vertex $e$ to vertex $b$, from vertex $b$ to vertex $b^2$, etc. If $a,b$ are generators, then there is a directed path $e, a, ba, aba $ from the identity vertex $e$ to vertex $aba$. The goal is to find a directed path from $e$ to $h$.

This can be done by constructing the Cayley graph and running a shortest path algorithm such as BFS to find a shortest $e-h$ path. The SAGE program below finds a shortest expression for $(4,5)$ as a product of elements from generator set $\{(1,2), (1,2,3,4,5), (1,5,4,3,2)\}$ - both the path and the arc labels (i.e. generator elements) are shown in the output below:

a = PermutationGroupElement('(1,2)')
b = PermutationGroupElement('(1,2,3,4,5)')
e = PermutationGroupElement('()')
S = [a,b, b.inverse()] #generators, closed under inverses
S5 = PermutationGroup(S)
G = S5.cayley_graph(generators=S) 
V = G.vertices()
p = G.shortest_path(V[0], V[1])
genterms = [p[i+1] * p[i].inverse() for i in range(len(p)-1)]
print("vertices on shortest path: \n" + str(p))
print("generators on shortest path: \n" + str(genterms))
Output:
vertices on shortest path: 
[(), (1,2,3,4,5), (1,3,5,2,4), (1,3,5)(2,4), (1,2,3,4), (4,5)]
generators on shortest path: 
[(1,2,3,4,5), (1,2,3,4,5), (4,5), (1,4,5,3,2), (1,4,5,3,2)]

Answer 2

It seems that your problem could be stated in terms of finding paths in Cayley Graphs, which might interest you:

Cayley Graph - Wikipedia