> < ^ From:

^ Subject:

Dear GAP-Forum,

Javaid Aslam asked:

> I suppose I may ask for an algorithm question not necessarily

> related to the GAP package...

Sure.

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

literature:

@book{butlerbuch, author = "G[regory] Butler", title = "Fundamental Algorithms for Permutation Groups", year = 1991, publisher = Springer, series = LNCS, volume = 559} @book{dixonmortimer, 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

@article{seress97, 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]