4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Simon May 29 at 8:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Display Name May 29 at 13:53
  • $\begingroup$ 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 ? $\endgroup$ – Simon May 29 at 14:13
  • $\begingroup$ 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. $\endgroup$ – Display Name May 29 at 14:21
  • $\begingroup$ 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. $\endgroup$ – Simon May 29 at 14:26
2
$\begingroup$

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)]
$\endgroup$
2
$\begingroup$

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

Cayley Graph - Wikipedia

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.