Efficient method of removing duplicacy in Lists in GAP

gapgroup-theory

Suppose that in GAP, a list is made up of certain conjugacy classes of a group $G$. Now, the list can contain same conjugacy class more than once, that is, there can be duplicacy. A standard method to remove duplicacy as far as I know is to write $S:=Set(K);$, where $K$ is our given list.

Is there any other efficient way to do this. A reason to ask this is if the conjugacy classes in the list $K$ are really large in size then the command $Set(K)$ , I suspect is not much efficient!

Thanks in advance for any kind of help!

Best Answer

Using Set will also aim to arrane in an (induced) total ordering, which can be expensive to compute. Unique removes duplicates without trying to sort, and is probably what you want to use

Related Solutions

[Math] Computing Conjugacy Classes of Subgroups in GAP

First, you may find helpful some functions like NormalSubgroups, IsomorphicSubgroups etc. which are listed in "How do I get the subgroups of my group?" entry from the GAP F.A.Q. There are also further functions not listed there, such as RepresentativesPerfectSubgroups, RepresentativesSimpleSubgroups, ConjugacyClassesMaximalSubgroups - see Chapter "Groups" from the GAP manual for more functions with the similar semantics.

Regarding p-subgroups, the manual entry for IsomorphicSubgroups suggests the same approach as in the Derek Holt's comment above: "To find p-subgroups it is often faster to compute the subgroup lattice of the Sylow subgroup".

Furthermore, LatticeByCyclicExtension and SubgroupsSolvableGroup accept optional arguments which allow to put restrictions on computed subgroups. In the latter case functions SizeConsiderFunction and ExactSizeConsiderFunction may be used. All four functions mentioned in this paragraph are documented in the Chapter "Groups", type e.g. ?SubgroupsSolvableGroup to see their descriptions in GAP.

As for tables of marks mentioned by Jack Schmidt, see Chapter "Tables of Marks" and in particular Section "Accessing Subgroups via Tables of Marks" - but that will work only for groups whose tables are contained in the tables of marks library.

Finite Groups – How to List Conjugacy Classes in GAP?

Let's create some group as an example:

gap> G:=Group((1,9,6,7,5)(2,10,3,8,4), (1,10,7,8)(2,9,4,6));
Group([ (1,9,6,7,5)(2,10,3,8,4), (1,10,7,8)(2,9,4,6) ])

It has 8 conjugacy classes of elements:

gap> cc:=ConjugacyClasses(G);
[ ()^G, (3,4,9,7)(5,8,6,10)^G, (3,5,9,6)(4,10,7,8)^G, (3,9)(4,7)(5,6)(8,10)^G,
  (2,3,9)(4,10,5)(6,8,7)^G, (1,2)(3,4,5,10,9,7,6,8)^G, 
  (1,2)(3,7,5,8,9,4,6,10)^G, (1,2,3,7,6)(4,8,5,9,10)^G ]
gap> Length(cc);
8

Let's take the 2nd of them:

gap> c:=cc[2];
(3,4,9,7)(5,8,6,10)^G

It contains 180 elements:

gap> Size(c);
180

and you can test membership of group elements in the conjugacy class as follows:

gap> (3,7,9,4)(5,10,6,8) in c;
true
gap> (3,7,6,8) in c;
false

Conjugacy class is not internally represented as a list of its elements - that would be very inefficient (for example, for algorithms that need only representatives of conjugacy classes). But if you need to get a list if all elements of the class, you can get them as follows:

gap> AsList(c);
[ (3,4,9,7)(5,8,6,10), (3,7,9,4)(5,10,6,8), (2,6,9,10)(4,7,8,5), 
  (2,10,9,6)(4,5,8,7), (2,10,7,5)(3,6,8,9), (2,5,7,10)(3,9,8,6), 
  (2,3,6,7)(4,9,10,8), (2,7,6,3)(4,8,10,9), (2,9,5,4)(3,8,10,7), 
  ...
  (1,9,6,10)(3,7,4,8), (1,10,6,9)(3,8,4,7), (1,3,4,10)(5,6,8,9), 
  (1,10,4,3)(5,9,8,6), (3,8,9,10)(4,5,7,6), (3,10,9,8)(4,6,7,5) ]

This may be very memory inefficient for large groups, but you can also iterate over its elements as follows:

gap> for x in c do
> Print(x,"\n");
> od;
( 3, 4, 9, 7)( 5, 8, 6,10)
( 3, 7, 9, 4)( 5,10, 6, 8)
...
( 3, 8, 9,10)( 4, 5, 7, 6)
( 3,10, 9, 8)( 4, 6, 7, 5)

without constructing the whole list, and also use enumerator which will give you a list-like behaviour:

gap> enum:=Enumerator(c);
<enumerator of (3,4,9,7)(5,8,6,10)^G>
gap> enum[2];
(3,7,9,4)(5,10,6,8)
gap> Position( enum, (3,7,9,4)(5,10,6,8) );
2
gap> Position( enum, (3,7,6,8) );
fail

also without constructing the whole list.

Best Answer

Related Solutions

[Math] Computing Conjugacy Classes of Subgroups in GAP

Finite Groups – How to List Conjugacy Classes in GAP?

Related Question