[GAP Forum] Cyclic permutation of five elements
Stephen C. Lipp
scl at edi-nola.com
Fri Apr 2 14:13:11 BST 2004
> 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
More information about the Forum
mailing list