[GAP Forum] Cyclic permutation of five elements
Stephen C. Lipp
scl at edi-nola.com
Wed Apr 7 22:07:58 BST 2004
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 transposition of the first two elements of the set, such a
transposition
walk does not exist. There is no way to walk from [1, 2, 3] through the
other
two equivalence classes and arrive back at [1, 2, 3] in three steps.
Stephen C. Lipp
More information about the Forum
mailing list