[GAP Forum] Cyclic permutation of five elements

[Stephen C. Lipp]

> Problem 1: Given five elements find a cyclic set of transpositions which
> will yield all permutations of these elements with respect to a given
> permutation, namely (2,3,4,5).
> 
> Unfortunately, I am not speaking of permutations in the traditional
> sense, but I am speaking of the indexing of the set.  Hence, if I apply
> the following transpositions
> 
> [<3,4>, <4,5>, <2,3>, <1,2>, <4,5>, <2,3>, <3,4>, <2,3>, <5,1>, <4,5>,
>  <1,2>, <3,4>, <2,3>, <3,4>, <1,2>, <5,1>, <1,2>, <4,5>, <5,1>, <4,5>,
>  <2,3>, <3,4>, <1,2>, <3,4>, <4,5>, <2,3>, <4,5>, <3,4>, <1,2>, <4,5>]
> 
> to the set [1,2,3,4,5] I get the cycle
> 
> [[1,2,4,3,5], [1,2,4,5,3], [1,4,2,5,3], [4,1,2,5,3], [4,1,2,3,5],
> [4,2,1,3,5],
>  [4,2,3,1,5], [4,3,2,1,5], [5,3,2,1,4], [5,3,2,4,1], [3,5,2,4,1],
> [3,5,4,2,1],
>  [3,4,5,2,1], [3,4,2,5,1], [4,3,2,5,1], [1,3,2,5,4], [3,1,2,5,4],
> [3,1,2,4,5],
>  [5,1,2,4,3], [5,1,2,3,4], [5,2,1,3,4], [5,2,3,1,4], [2,5,3,1,4],
> [2,5,1,3,4],
>  [2,5,1,4,3], [2,1,5,4,3], [2,1,5,3,4], [2,1,3,5,4], [1,2,3,5,4],
> [1,2,3,4,5]]
> 
> The set of transpositions was obtained using an algorithm on a
> spreadsheet with a random number generator.
> 
> This cycle contains all 5!/4 permutations of 5 elements where the last 4
> elements are allowed to rotate.  The terminology I am using would
> indicate there exists an isomorphism between the index transpositions
> and group permutations.  Does such an isomorphism exist and, if so, what
> is it?

Let me try to guess what you want to say:

Apparently you describe a walk through the Cayley graph of the
symmetric group S_5 with the set of transpositions as generating set
which passes each element of the conjugacy class of the 4-cycles
exactly once.

The isomorphism you are looking for is probably just the
action isomorphism for the action of S_5 on the set {1,2,3,4,5}.

Please don't hesitate to ask in case I have misunderstood you or
if you have further questions.

Hope this helps,

    Stefan Kohl

------------------------------------------------------------------------

So I am looking for a cyclic walk through the Cayley table of 120 elements where the equivalence classes are with respect to rotation on the last 4 elements of the set.  Hence there are 30 steps taken to cover all the classes.  The obvious question that arises is,

How does one find a "walk" through this set?

As pointed out in the initial E-mail, the walk was found using an algorithm (basically a depth-first search) on a spreadsheet with a random number generator.  Now suppose the set is larger (the Cayley table is 5040 elements where the equivalence classes are with respect to a rotation of order 3).  Hence there are 1680 steps taken to cover all the partitions of the set.  Is there a more efficient algorithm than a depth-first search?

The other question that has not been addressed is existence.  Does such a walk exist?  If, for example, I try to walk through S_3 where the equivalence class is with respect to transposition of the first two elements of the set, such a transposition walk does not exist.

Stephen C. Lipp