Dear Gap Forum,
Thank you for your references.
It seems I failed to state the problem clearly; the main problem
is :
HOW TO REPRESENT EACH GROUP ELEMENT pi AS PRODUCT OF mutually
DISJOINT PERMUTATIONS TAKEN FROM A PRE-DEFINED SET OF
permutations of POLYNOMIAL SIZE.
Here I need *not* enumerate all or some of the elements, but I may need
any arbitrary pi in G. Also, no conversion from non-disjoint to
disjoint permutation product should be necessary.
Let me refresh the whole scenario/background:
The most common technique, I assume, for representing a permutation
group
is by a set of strong generators which produce a "representaion matrix",
where ecah row contains a right/left traversal of a subgroup
in a sub-group tower
(also called stablizer chain). In such a situation the complete group G
can be represented by a set theoretic expresiion of the form:
G = R1 X R2 X ... Rn, where Ri is a set containing right(left) traversal in a sub-group tower: G= G0 > G1 > G2 > ... > Gn = I, Gi being a subgroup of G(i-1), and the n-tuple (r1, r2, r3 ... rn) from R1 X R2 X ... Rn would imply the product r1*r2*r3 ... rn, where ri is in Ri.
In this case any element pi in G can be represented as
pi = r1*r2*r3 ... *rn.
The **problem** here is that permutations, r1 ... rn, are not
necessarily disjoint.
Now the question is whether any set-theoretic expression of polynomial
size can be found (in polynomial time) such that all permutations ri
are mutually disjoint.
One possible form of this set-theo expression could be:
SUM( Ri1 X Ri2 X ... Rin), i = 1.. n^k, for some constant k.
David Joyner wrote: > > Dear Gap Forum: > > > Mr. Aslam wrote: > > > > ------------------------- > > Dear Gap Forum, > > > > I am looking for an algorithm(s) that would enumerate > > a permutation group (from a set of genrators) such > > that each element of the > > group is represented as a product of the disjoint permutations > > (which would be from the set of the generators). > > > > That is if each element pi of the group G is represented as > > pi = g1*g2* ... gr , > > (where r is clearly a polynomial in the degree of the group), > > > > then g1,g2, .. gr are mutually disjoint. > > > > Here the size of set of generators could be a polynomial in r. > > Clearly, it is not important whether the generators are strong are not. > > > > Hope to receive some references in this direction. > > See > Gray Codes for Reflection Groups, J. H. Conway, N. J. A. Sloane and A. R. Wilks, > > Graphs and Combinatorics, > 5 (1989), pp. 315-325. > available at > http://www.research.att.com/~njas/doc/gp.html > > > > > > > Thanking you all. > > ------------------------------ > > > > -- > David Joyner, Assoc Prof of Math > US Naval Academy, Annapolis, MD 21402 > (410)293-6738 > wdj@nadn.navy.mil > http://web.usna.navy.mil/~wdj/homepage.html > ++++++++++++++++++++++++++++++++++++++++++++ > "A Mathematician is a machine for turning > coffee into theorems." Alfred Renyi -- ================================================= Javaid Aslam jaslamx@ichips.intel.com Architecture Validation Tools, Intel Corp. MS AL4-51 Location : AL4 2nd. Floor (near N5). Office Phone : 503-591-4735 Fax: 503-591-4862