> < ^ Date: Mon, 04 May 1998 11:04:53 +0100 (BST)
> < ^ From: Alexander Hulpke <hulpke@math.colostate.edu >
^ Subject: re: Enumerating Group elements from Strong Generators

Dear GAP-Forum,

Javaid Aslam asked:

> I suppose I may ask for an algorithm question not necessarily
> related to the GAP package...

I am trying to find an algorithm (and possibly a good reference) for
enumerating group elements
(e.g. from a representation matrix of strong generators).
The strong generators (fairly well known) are for the
symmetric group Sn:

{(1, 2, 3, ... , n) ,(2, 3, ... , n), (3, ... , n), ... (n-1, n) }

The general process for enumerating group elements from strong generators
uses a stabilizer chain. These were introduced by Charles Sims, but the
original article may be a bit difficult to find in your library.
Therefore I suggest you look in one of the following two books, which
provide an introduction (though they don't go into details of the
implementation). Both also give reference to the original works in the

         author  = "G[regory] Butler",
         title   = "Fundamental Algorithms for Permutation Groups",
         year    = 1991,
         publisher = Springer,
         series  = LNCS,
         volume  = 559}

         author    = "John~D. Dixon and Brian Mortimer",
         title     = "Permutation Groups",
         publisher = Springer,
         series    = GTM,
         volume    = 163,
         year      = 1996}
(chapter 3 here contains a section on computational methods.)

The article

         author    = "{\'A}kos Seress",
         title     = "An introduction to Computational Group Theory",
         journal   = "Notices AMS",
         year      = 1997,
         volume    = 44,
         number    = 6,
         pages     = "671--679"}

is also well worth reading.

Finally let me remark, that as long as you are only considering the
symmetric group, there are easier (purely combinatorial) algorithms to
enumerate all permutations in the symmetric group.

Best regards,

Alexander Hulpke

> < [top]