Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - perm.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 20459-9710128) Lines: 587 630 93.2 %
Date: 2017-04-28 05:33:48 Functions: 68 71 95.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000-2003  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /*************************************************************************/
      18             : /**                                                                     **/
      19             : /**                   Routines for handling VEC/COL                     **/
      20             : /**                                                                     **/
      21             : /*************************************************************************/
      22             : int
      23        4080 : vec_isconst(GEN v)
      24             : {
      25        4080 :   long i, l = lg(v);
      26             :   GEN w;
      27        4080 :   if (l==1) return 1;
      28        4080 :   w = gel(v,1);
      29        8658 :   for(i=2;i<l;i++)
      30        7296 :     if (!gequal(gel(v,i), w)) return 0;
      31        1362 :   return 1;
      32             : }
      33             : 
      34             : /* Check if all the elements of v are different.
      35             :  * Use a quadratic algorithm. Could be done in n*log(n) by sorting. */
      36             : int
      37        2160 : vec_is1to1(GEN v)
      38             : {
      39        2160 :   long i, j, l = lg(v);
      40       13848 :   for (i=1; i<l; i++)
      41             :   {
      42       11808 :     GEN w = gel(v,i);
      43       77742 :     for(j=i+1; j<l; j++)
      44       66054 :       if (gequal(gel(v,j), w)) return 0;
      45             :   }
      46        2040 :   return 1;
      47             : }
      48             : 
      49             : GEN
      50       64836 : vec_insert(GEN v, long n, GEN x)
      51             : {
      52       64836 :   long i, l=lg(v);
      53       64836 :   GEN V = cgetg(l+1,t_VEC);
      54       64836 :   for(i=1; i<n; i++) gel(V,i) = gel(v,i);
      55       64836 :   gel(V,n) = x;
      56       64836 :   for(i=n+1; i<=l; i++) gel(V,i) = gel(v,i-1);
      57       64836 :   return V;
      58             : }
      59             : /*************************************************************************/
      60             : /**                                                                     **/
      61             : /**                   Routines for handling VECSMALL                    **/
      62             : /**                                                                     **/
      63             : /*************************************************************************/
      64             : /* Sort v[0]...v[n-1] and put result in w[0]...w[n-1].
      65             :  * We accept v==w. w must be allocated. */
      66             : static void
      67     2393891 : vecsmall_sortspec(GEN v, long n, GEN w)
      68             : {
      69     2393891 :   pari_sp ltop=avma;
      70     2393891 :   long nx=n>>1, ny=n-nx;
      71             :   long m, ix, iy;
      72             :   GEN x, y;
      73     2393891 :   if (n<=2)
      74             :   {
      75     1598122 :     if (n==1)
      76      416419 :       w[0]=v[0];
      77     1181703 :     else if (n==2)
      78             :     {
      79     1181704 :       long v0=v[0], v1=v[1];
      80     1181704 :       if (v0<=v1) { w[0]=v0; w[1]=v1; }
      81      918613 :       else        { w[0]=v1; w[1]=v0; }
      82             :     }
      83     3992016 :     return;
      84             :   }
      85      795769 :   x=new_chunk(nx); y=new_chunk(ny);
      86      795771 :   vecsmall_sortspec(v,nx,x);
      87      795772 :   vecsmall_sortspec(v+nx,ny,y);
      88     4539263 :   for (m=0, ix=0, iy=0; ix<nx && iy<ny; )
      89     2947719 :     if (x[ix]<=y[iy])
      90      933329 :       w[m++]=x[ix++];
      91             :     else
      92     2014390 :       w[m++]=y[iy++];
      93      795772 :   for(;ix<nx;) w[m++]=x[ix++];
      94      795772 :   for(;iy<ny;) w[m++]=y[iy++];
      95      795772 :   avma=ltop;
      96             : }
      97             : 
      98             : /*in place sort.*/
      99             : void
     100     4877499 : vecsmall_sort(GEN V)
     101             : {
     102     4877499 :   long l = lg(V)-1;
     103     9755001 :   if (l<=1) return;
     104      802346 :   vecsmall_sortspec(V+1,l,V+1);
     105             : }
     106             : 
     107             : /* cf gen_sortspec */
     108             : static GEN
     109    15365752 : vecsmall_indexsortspec(GEN v, long n)
     110             : {
     111             :   long nx, ny, m, ix, iy;
     112             :   GEN x, y, w;
     113    15365752 :   switch(n)
     114             :   {
     115       35022 :     case 1: return mkvecsmall(1);
     116     4583900 :     case 2: return (v[1] <= v[2])? mkvecsmall2(1,2): mkvecsmall2(2,1);
     117             :     case 3:
     118     4049039 :       if (v[1] <= v[2]) {
     119     3519191 :         if (v[2] <= v[3]) return mkvecsmall3(1,2,3);
     120     1687240 :         return (v[1] <= v[3])? mkvecsmall3(1,3,2)
     121      843620 :                              : mkvecsmall3(3,1,2);
     122             :       } else {
     123      529848 :         if (v[1] <= v[3]) return mkvecsmall3(2,1,3);
     124      709544 :         return (v[2] <= v[3])? mkvecsmall3(2,3,1)
     125      354772 :                              : mkvecsmall3(3,2,1);
     126             :       }
     127             :   }
     128     6697791 :   nx = n>>1; ny = n-nx;
     129     6697791 :   w = cgetg(n+1,t_VECSMALL);
     130     6697792 :   x = vecsmall_indexsortspec(v,nx);
     131     6697792 :   y = vecsmall_indexsortspec(v+nx,ny);
     132   112518433 :   for (m=1, ix=1, iy=1; ix<=nx && iy<=ny; )
     133    99122849 :     if (v[x[ix]] <= v[y[iy]+nx])
     134    63966792 :       w[m++] = x[ix++];
     135             :     else
     136    35156057 :       w[m++] = y[iy++]+nx;
     137     6697792 :   for(;ix<=nx;) w[m++] = x[ix++];
     138     6697792 :   for(;iy<=ny;) w[m++] = y[iy++]+nx;
     139     6697792 :   avma = (pari_sp)w; return w;
     140             : }
     141             : 
     142             : /*indirect sort.*/
     143             : GEN
     144     1970169 : vecsmall_indexsort(GEN V)
     145             : {
     146     1970169 :   long l=lg(V)-1;
     147     1970169 :   if (l==0) return cgetg(1, t_VECSMALL);
     148     1970169 :   return vecsmall_indexsortspec(V,l);
     149             : }
     150             : 
     151             : /* assume V sorted */
     152             : GEN
     153        1152 : vecsmall_uniq_sorted(GEN V)
     154             : {
     155             :   GEN W;
     156        1152 :   long i,j, l = lg(V);
     157        1152 :   if (l == 1) return vecsmall_copy(V);
     158        1152 :   W = cgetg(l,t_VECSMALL);
     159        1152 :   W[1] = V[1];
     160        2238 :   for(i=j=2; i<l; i++)
     161        1086 :     if (V[i] != W[j-1]) W[j++] = V[i];
     162        1152 :   stackdummy((pari_sp)(W + l), (pari_sp)(W + j));
     163        1152 :   setlg(W, j); return W;
     164             : }
     165             : 
     166             : GEN
     167        1152 : vecsmall_uniq(GEN V)
     168             : {
     169        1152 :   pari_sp av = avma;
     170        1152 :   V = zv_copy(V); vecsmall_sort(V);
     171        1152 :   return gerepileuptoleaf(av, vecsmall_uniq_sorted(V));
     172             : }
     173             : 
     174             : /* assume x sorted */
     175             : long
     176           0 : vecsmall_duplicate_sorted(GEN x)
     177             : {
     178           0 :   long i,k,l=lg(x);
     179           0 :   if (l==1) return 0;
     180           0 :   for (k=x[1],i=2; i<l; k=x[i++])
     181           0 :     if (x[i] == k) return i;
     182           0 :   return 0;
     183             : }
     184             : 
     185             : long
     186       10184 : vecsmall_duplicate(GEN x)
     187             : {
     188       10184 :   pari_sp av=avma;
     189       10184 :   GEN p=vecsmall_indexsort(x);
     190       10184 :   long k,i,r=0,l=lg(x);
     191       10184 :   if (l==1) return 0;
     192       13764 :   for (k=x[p[1]],i=2; i<l; k=x[p[i++]])
     193        3580 :     if (x[p[i]] == k) { r=p[i]; break; }
     194       10184 :   avma=av;
     195       10184 :   return r;
     196             : }
     197             : 
     198             : /*************************************************************************/
     199             : /**                                                                     **/
     200             : /**             Routines for handling vectors of VECSMALL               **/
     201             : /**                                                                     **/
     202             : /*************************************************************************/
     203             : 
     204             : GEN
     205       98556 : vecvecsmall_sort(GEN x)
     206             : {
     207       98556 :   return gen_sort(x, (void*)&vecsmall_lexcmp, cmp_nodata);
     208             : }
     209             : 
     210             : GEN
     211         276 : vecvecsmall_sort_uniq(GEN x)
     212             : {
     213         276 :   return gen_sort_uniq(x, (void*)&vecsmall_lexcmp, cmp_nodata);
     214             : }
     215             : 
     216             : GEN
     217          18 : vecvecsmall_indexsort(GEN x)
     218             : {
     219          18 :   return gen_indexsort(x, (void*)&vecsmall_lexcmp, cmp_nodata);
     220             : }
     221             : 
     222             : long
     223    11944434 : vecvecsmall_search(GEN x, GEN y, long flag)
     224             : {
     225    11944434 :   return gen_search(x,y,flag,(void*)vecsmall_prefixcmp, cmp_nodata);
     226             : }
     227             : 
     228             : /* assume x non empty */
     229             : long
     230         114 : vecvecsmall_max(GEN x)
     231             : {
     232         114 :   long i, l = lg(x), m = vecsmall_max(gel(x,1));
     233         942 :   for (i = 2; i < l; i++)
     234             :   {
     235         828 :     long t = vecsmall_max(gel(x,i));
     236         828 :     if (t > m) m = t;
     237             :   }
     238         114 :   return m;
     239             : }
     240             : 
     241             : /*************************************************************************/
     242             : /**                                                                     **/
     243             : /**                  Routines for handling permutations                 **/
     244             : /**                                                                     **/
     245             : /*************************************************************************/
     246             : 
     247             : /* Permutations may be given by
     248             :  * perm (VECSMALL): a bijection from 1...n to 1...n i-->perm[i]
     249             :  * cyc (VEC of VECSMALL): a product of disjoint cycles. */
     250             : 
     251             : /* Multiply (compose) two permutations, putting the result in the second one. */
     252             : static void
     253           6 : perm_mul_inplace2(GEN s, GEN t)
     254             : {
     255           6 :   long i, l = lg(s);
     256           6 :   for (i = 1; i < l; i++) t[i] = s[t[i]];
     257           6 : }
     258             : 
     259             : /* Orbits of the subgroup generated by v on {1,..,n} */
     260             : static GEN
     261       96456 : vecperm_orbits_i(GEN v, long n)
     262             : {
     263       96456 :   long mj = 1, lv = lg(v), k, l;
     264       96456 :   GEN cycle = cgetg(n+1, t_VEC), bit = const_vecsmall(n, 0);
     265     1131900 :   for (k = 1, l = 1; k <= n;)
     266             :   {
     267      938988 :     long m = 1;
     268      938988 :     GEN cy = cgetg(n+1, t_VECSMALL);
     269      938988 :     for (  ; bit[mj]; mj++) /*empty*/;
     270      938988 :     k++; cy[m++] = mj;
     271      938988 :     bit[mj++] = 1;
     272             :     for(;;)
     273             :     {
     274     1542918 :       long o, mold = m;
     275     3088404 :       for (o = 1; o < lv; o++)
     276             :       {
     277     1545486 :         GEN vo = gel(v,o);
     278             :         long p;
     279     6502830 :         for (p = 1; p < m; p++) /* m increases! */
     280             :         {
     281     4957344 :           long j = vo[ cy[p] ];
     282     4957344 :           if (!bit[j]) cy[m++] = j;
     283     4957344 :           bit[j] = 1;
     284             :         }
     285             :       }
     286     1542918 :       if (m == mold) break;
     287      603930 :       k += m - mold;
     288      603930 :     }
     289      938988 :     setlg(cy, m); gel(cycle,l++) = cy;
     290             :   }
     291       96456 :   setlg(cycle, l); return cycle;
     292             : }
     293             : /* memory clean version */
     294             : GEN
     295         684 : vecperm_orbits(GEN v, long n)
     296             : {
     297         684 :   pari_sp av = avma;
     298         684 :   return gerepilecopy(av, vecperm_orbits_i(v, n));
     299             : }
     300             : 
     301             : /* Compute the cyclic decomposition of a permutation */
     302             : GEN
     303        3096 : perm_cycles(GEN v)
     304             : {
     305        3096 :   pari_sp av = avma;
     306        3096 :   return gerepilecopy(av, vecperm_orbits_i(mkvec(v), lg(v)-1));
     307             : }
     308             : 
     309             : static long
     310         144 : isperm(GEN v)
     311             : {
     312         144 :   long i, l = lg(v)-1;
     313         144 :   if (typ(v)!=t_VECSMALL) return 0;
     314        1872 :   for (i=1; i<=l; i++)
     315        1728 :     if (v[i]<1 || v[i]>l) return 0;
     316         144 :   return 1;
     317             : }
     318             : 
     319             : /* Output the order of p */
     320             : long
     321       70428 : perm_order(GEN v)
     322             : {
     323       70428 :   pari_sp ltop = avma;
     324       70428 :   GEN c = vecperm_orbits_i(mkvec(v), lg(v)-1);
     325             :   long i, d;
     326       70428 :   for(i=1, d=1; i<lg(c); i++) d = clcm(d, lg(gel(c,i))-1);
     327       70428 :   avma = ltop; return d;
     328             : }
     329             : 
     330             : long
     331          72 : permorder(GEN v)
     332             : {
     333          72 :   if (!isperm(v)) pari_err_TYPE("permorder",v);
     334          72 :   return perm_order(v);
     335             : }
     336             : 
     337             : /* sign of a permutation */
     338             : long
     339       22248 : perm_sign(GEN v)
     340             : {
     341       22248 :   pari_sp av = avma;
     342       22248 :   GEN c = vecperm_orbits_i(mkvec(v), lg(v)-1);
     343       22248 :   long i, l = lg(c), s = 1;
     344      222606 :   for (i = 1; i < l; i++)
     345      200358 :     if (odd(lg(gel(c, i)))) s = -s;
     346       22248 :   avma = av; return s;
     347             : }
     348             : 
     349             : long
     350          72 : permsign(GEN v)
     351             : {
     352          72 :   if (!isperm(v)) pari_err_TYPE("permorder",v);
     353          72 :   return perm_sign(v);
     354             : }
     355             : 
     356             : GEN
     357        1476 : cyc_pow(GEN cyc, long exp)
     358             : {
     359             :   long i, j, k, l, r;
     360             :   GEN c;
     361        5112 :   for (r = j = 1; j < lg(cyc); j++)
     362             :   {
     363        3636 :     long n = lg(gel(cyc,j)) - 1;
     364        3636 :     r += cgcd(n, exp);
     365             :   }
     366        1476 :   c = cgetg(r, t_VEC);
     367        5112 :   for (r = j = 1; j < lg(cyc); j++)
     368             :   {
     369        3636 :     GEN v = gel(cyc,j);
     370        3636 :     long n = lg(v) - 1, e = smodss(exp,n), g = (long)ugcd(n, e), m = n / g;
     371        7974 :     for (i = 0; i < g; i++)
     372             :     {
     373        4338 :       GEN p = cgetg(m+1, t_VECSMALL);
     374        4338 :       gel(c,r++) = p;
     375       14700 :       for (k = 1, l = i; k <= m; k++)
     376             :       {
     377       10362 :         p[k] = v[l+1];
     378       10362 :         l += e; if (l >= n) l -= n;
     379             :       }
     380             :     }
     381             :   }
     382        1476 :   return c;
     383             : }
     384             : 
     385             : /* Compute the power of a permutation given by product of cycles
     386             :  * Ouput a perm, not a cyc */
     387             : GEN
     388           0 : cyc_pow_perm(GEN cyc, long exp)
     389             : {
     390             :   long e, j, k, l, n;
     391             :   GEN p;
     392           0 :   for (n = 0, j = 1; j < lg(cyc); j++) n += lg(gel(cyc,j))-1;
     393           0 :   p = cgetg(n + 1, t_VECSMALL);
     394           0 :   for (j = 1; j < lg(cyc); j++)
     395             :   {
     396           0 :     GEN v = gel(cyc,j);
     397           0 :     n = lg(v) - 1; e = smodss(exp, n);
     398           0 :     for (k = 1, l = e; k <= n; k++)
     399             :     {
     400           0 :       p[v[k]] = v[l+1];
     401           0 :       if (++l == n) l = 0;
     402             :     }
     403             :   }
     404           0 :   return p;
     405             : }
     406             : 
     407             : GEN
     408        5544 : perm_pow(GEN perm, long exp)
     409             : {
     410        5544 :   long i, r = lg(perm)-1;
     411        5544 :   GEN p = zero_zv(r);
     412        5544 :   pari_sp av = avma;
     413        5544 :   GEN v = cgetg(r+1, t_VECSMALL);
     414      108696 :   for (i=1; i<=r; i++)
     415             :   {
     416             :     long e, n, k, l;
     417      103152 :     if (p[i]) continue;
     418       39864 :     v[1] = i;
     419      103152 :     for (n=1, k=perm[i]; k!=i; k=perm[k], n++)
     420       63288 :       v[n+1] = k;
     421       39864 :     e = smodss(exp, n);
     422      143016 :     for (k = 1, l = e; k <= n; k++)
     423             :     {
     424      103152 :       p[v[k]] = v[l+1];
     425      103152 :       if (++l == n) l = 0;
     426             :     }
     427             :   }
     428        5544 :   avma = av; return p;
     429             : }
     430             : 
     431             : static GEN
     432          18 : perm_to_GAP(GEN p)
     433             : {
     434          18 :   pari_sp ltop=avma;
     435             :   GEN gap;
     436             :   GEN x;
     437             :   long i;
     438          18 :   long nb, c=0;
     439             :   char *s;
     440             :   long sz;
     441          18 :   long lp=lg(p)-1;
     442          18 :   if (typ(p) != t_VECSMALL)  pari_err_TYPE("perm_to_GAP",p);
     443          18 :   x = perm_cycles(p);
     444          18 :   sz = (long) ((bfffo(lp)+1) * LOG10_2 + 1);
     445             :   /*Dry run*/
     446         114 :   for (i = 1, nb = 1; i < lg(x); ++i)
     447             :   {
     448          96 :     GEN z = gel(x,i);
     449          96 :     long lz = lg(z)-1;
     450          96 :     nb += 1+lz*(sz+2);
     451             :   }
     452          18 :   nb++;
     453             :   /*Real run*/
     454          18 :   gap = cgetg(nchar2nlong(nb) + 1, t_STR);
     455          18 :   s = GSTR(gap);
     456         114 :   for (i = 1; i < lg(x); ++i)
     457             :   {
     458             :     long j;
     459          96 :     GEN z = gel(x,i);
     460          96 :     if (lg(z) > 2)
     461             :     {
     462          96 :       s[c++] = '(';
     463         312 :       for (j = 1; j < lg(z); ++j)
     464             :       {
     465         216 :         if (j > 1)
     466             :         {
     467         120 :           s[c++] = ','; s[c++] = ' ';
     468             :         }
     469         216 :         sprintf(s+c,"%ld",z[j]);
     470         216 :         while(s[c++]) /* empty */;
     471         216 :         c--;
     472             :       }
     473          96 :       s[c++] = ')';
     474             :     }
     475             :   }
     476          18 :   if (!c) { s[c++]='('; s[c++]=')'; }
     477          18 :   s[c] = '\0';
     478          18 :   return gerepileupto(ltop,gap);
     479             : }
     480             : 
     481             : int
     482      460056 : perm_commute(GEN s, GEN t)
     483             : {
     484      460056 :   long i, l = lg(t);
     485    32892408 :   for (i = 1; i < l; i++)
     486    32444160 :     if (t[ s[i] ] != s[ t[i] ]) return 0;
     487      448248 :   return 1;
     488             : }
     489             : 
     490             : /*************************************************************************/
     491             : /**                                                                     **/
     492             : /**                  Routines for handling groups                       **/
     493             : /**                                                                     **/
     494             : /*************************************************************************/
     495             : /* A Group is a t_VEC [gen,orders]
     496             :  * gen (vecvecsmall): list of generators given by permutations
     497             :  * orders (vecsmall): relatives orders of generators. */
     498      335232 : INLINE GEN grp_get_gen(GEN G) { return gel(G,1); }
     499      574326 : INLINE GEN grp_get_ord(GEN G) { return gel(G,2); }
     500             : 
     501             : /* A Quotient Group is a t_VEC [gen,coset]
     502             :  * gen (vecvecsmall): coset generators
     503             :  * coset (vecsmall): gen[coset[p[1]]] generate the p-coset.
     504             :  */
     505       57252 : INLINE GEN quo_get_gen(GEN C) { return gel(C,1); }
     506        8688 : INLINE GEN quo_get_coset(GEN C) { return gel(C,2); }
     507             : 
     508             : static GEN
     509       23304 : trivialsubgroups(void)
     510       23304 : { GEN L = cgetg(2, t_VEC); gel(L,1) = trivialgroup(); return L; }
     511             : 
     512             : /* Compute the order of p modulo the group given by a set */
     513             : long
     514       95934 : perm_relorder(GEN p, GEN set)
     515             : {
     516       95934 :   pari_sp ltop = avma;
     517       95934 :   long n = 1;
     518       95934 :   long q = p[1];
     519       95934 :   while (!F2v_coeff(set,q)) { q = p[q]; n++; }
     520       95934 :   avma = ltop; return n;
     521             : }
     522             : 
     523             : GEN
     524        5940 : perm_generate(GEN S, GEN H, long o)
     525             : {
     526        5940 :   long i, n = lg(H)-1;
     527        5940 :   GEN L = cgetg(n*o + 1, t_VEC);
     528        5940 :   for(i=1; i<=n;     i++) gel(L,i) = vecsmall_copy(gel(H,i));
     529        5940 :   for(   ; i <= n*o; i++) gel(L,i) = perm_mul(gel(L,i-n), S);
     530        5940 :   return L;
     531             : }
     532             : 
     533             : /*Return the order (cardinality) of a group */
     534             : long
     535      248010 : group_order(GEN G)
     536             : {
     537      248010 :   return zv_prod(grp_get_ord(G));
     538             : }
     539             : 
     540             : /* G being a subgroup of S_n, output n */
     541             : long
     542        4704 : group_domain(GEN G)
     543             : {
     544        4704 :   GEN gen = grp_get_gen(G);
     545        4704 :   if (lg(gen) < 2) pari_err_DOMAIN("group_domain", "#G", "=", gen_1,G);
     546        4704 :   return lg(gel(gen,1)) - 1;
     547             : }
     548             : 
     549             : /*Left coset of g mod G: gG*/
     550             : GEN
     551      109764 : group_leftcoset(GEN G, GEN g)
     552             : {
     553      109764 :   GEN gen = grp_get_gen(G), ord = grp_get_ord(G);
     554      109764 :   GEN res = cgetg(group_order(G)+1, t_VEC);
     555             :   long i, j, k;
     556      109764 :   gel(res,1) = vecsmall_copy(g);
     557      109764 :   k = 1;
     558      205194 :   for (i = 1; i < lg(gen); i++)
     559             :   {
     560       95430 :     long c = k * (ord[i] - 1);
     561       95430 :     for (j = 1; j <= c; j++) gel(res,++k) = perm_mul(gel(res,j), gel(gen,i));
     562             :   }
     563      109764 :   return res;
     564             : }
     565             : /*Right coset of g mod G: Gg*/
     566             : GEN
     567       49242 : group_rightcoset(GEN G, GEN g)
     568             : {
     569       49242 :   GEN gen = grp_get_gen(G), ord = grp_get_ord(G);
     570       49242 :   GEN res = cgetg(group_order(G)+1, t_VEC);
     571             :   long i, j, k;
     572       49242 :   gel(res,1) = vecsmall_copy(g);
     573       49242 :   k = 1;
     574       84054 :   for (i = 1; i < lg(gen); i++)
     575             :   {
     576       34812 :     long c = k * (ord[i] - 1);
     577       34812 :     for (j = 1; j <= c; j++) gel(res,++k) = perm_mul(gel(gen,i), gel(res,j));
     578             :   }
     579       49242 :   return res;
     580             : }
     581             : /*Elements of a group from the generators, cf group_leftcoset*/
     582             : GEN
     583       49302 : group_elts(GEN G, long n)
     584             : {
     585       49302 :   GEN gen = grp_get_gen(G), ord = grp_get_ord(G);
     586       49302 :   GEN res = cgetg(group_order(G)+1, t_VEC);
     587             :   long i, j, k;
     588       49302 :   gel(res,1) = identity_perm(n);
     589       49302 :   k = 1;
     590       97788 :   for (i = 1; i < lg(gen); i++)
     591             :   {
     592       48486 :     long c = k * (ord[i] - 1);
     593             :     /* j = 1, use res[1] = identity */
     594       48486 :     gel(res,++k) = vecsmall_copy(gel(gen,i));
     595       48486 :     for (j = 2; j <= c; j++) gel(res,++k) = perm_mul(gel(res,j), gel(gen,i));
     596             :   }
     597       49302 :   return res;
     598             : }
     599             : 
     600             : GEN
     601        9252 : groupelts_set(GEN elts, long n)
     602             : {
     603        9252 :   GEN res = zero_F2v(n);
     604        9252 :   long i, l = lg(elts);
     605       50046 :   for(i=1; i<l; i++)
     606       40794 :     F2v_set(res,mael(elts,i,1));
     607        9252 :   return res;
     608             : }
     609             : 
     610             : /*Elements of a group from the generators, returned as a set (bitmap)*/
     611             : GEN
     612       43176 : group_set(GEN G, long n)
     613             : {
     614       43176 :   GEN res = zero_F2v(n);
     615       43176 :   pari_sp av = avma;
     616       43176 :   GEN elts = group_elts(G, n);
     617       43176 :   long i, l = lg(elts);
     618      135546 :   for(i=1; i<l; i++)
     619       92370 :     F2v_set(res,mael(elts,i,1));
     620       43176 :   avma = av;
     621       43176 :   return res;
     622             : }
     623             : 
     624             : static int
     625        1314 : sgcmp(GEN a, GEN b) { return vecsmall_lexcmp(gel(a,1),gel(b,1)); }
     626             : 
     627             : GEN
     628          18 : subgroups_tableset(GEN S, long n)
     629             : {
     630          18 :   long i, l = lg(S);
     631          18 :   GEN  v = cgetg(l, t_VEC);
     632         330 :   for(i=1; i<l; i++)
     633         312 :     gel(v,i) = mkvec2(group_set(gel(S,i), n), mkvecsmall(i));
     634          18 :   gen_sort_inplace(v,(void*)sgcmp,cmp_nodata, NULL);
     635          18 :   return v;
     636             : }
     637             : 
     638             : long
     639         102 : tableset_find_index(GEN tbl, GEN set)
     640             : {
     641         102 :   long i = tablesearch(tbl,mkvec2(set,mkvecsmall(0)),sgcmp);
     642         102 :   if (!i) return 0;
     643         102 :   return mael3(tbl,i,2,1);
     644             : }
     645             : 
     646             : GEN
     647       23304 : trivialgroup(void) { retmkvec2(cgetg(1,t_VEC), cgetg(1,t_VECSMALL)); }
     648             : /*Cyclic group generated by g of order s*/
     649             : GEN
     650        3438 : cyclicgroup(GEN g, long s)
     651        3438 : { retmkvec2(mkvec( vecsmall_copy(g) ),
     652             :             mkvecsmall(s)); }
     653             : /*Return the group generated by g1,g2 of relative orders s1,s2*/
     654             : GEN
     655          66 : dicyclicgroup(GEN g1, GEN g2, long s1, long s2)
     656          66 : { retmkvec2( mkvec2(vecsmall_copy(g1), vecsmall_copy(g2)),
     657             :              mkvecsmall2(s1, s2) ); }
     658             : 
     659             : /* return the quotient map G --> G/H */
     660             : /*The ouput is [gen,hash]*/
     661             : /* gen (vecvecsmall): coset generators
     662             :  * coset (vecsmall): vecsmall of coset number) */
     663             : GEN
     664        3318 : group_quotient(GEN G, GEN H)
     665             : {
     666        3318 :   pari_sp ltop = avma;
     667             :   GEN  p2, p3;
     668        3318 :   long i, j, a = 1;
     669        3318 :   long n = group_domain(G), o = group_order(H);
     670        3318 :   GEN  elt = group_elts(G,n), el;
     671        3318 :   long le = lg(elt)-1;
     672        3318 :   GEN used = zero_F2v(le+1);
     673        3318 :   long l = le/o;
     674        3318 :   p2 = cgetg(l+1, t_VEC);
     675        3318 :   p3 = zero_zv(n);
     676        3318 :   el = zero_zv(n);
     677       52230 :   for (i = 1; i<=le; i++)
     678       48912 :     el[mael(elt,i,1)]=i;
     679       27240 :   for (i = 1; i <= l; ++i)
     680             :   {
     681             :     GEN V;
     682       23928 :     while(F2v_coeff(used,a)) a++;
     683       23928 :     V = group_leftcoset(H,gel(elt,a));
     684       23928 :     gel(p2,i) = gel(V,1);
     685       72750 :     for(j=1;j<lg(V);j++)
     686             :     {
     687       48828 :       long b = el[mael(V,j,1)];
     688       48828 :       if (b==0) pari_err_IMPL("group_quotient for a non-WSS group");
     689       48822 :       F2v_set(used,b);
     690             :     }
     691       72738 :     for (j = 1; j <= o; j++)
     692       48816 :       p3[mael(V, j, 1)] = i;
     693             :   }
     694        3312 :   return gerepilecopy(ltop,mkvec2(p2,p3));
     695             : }
     696             : 
     697             : /*Compute the image of a permutation by a quotient map.*/
     698             : GEN
     699        8688 : quotient_perm(GEN C, GEN p)
     700             : {
     701        8688 :   GEN gen = quo_get_gen(C);
     702        8688 :   GEN coset = quo_get_coset(C);
     703        8688 :   long j, l = lg(gen);
     704        8688 :   GEN p3 = cgetg(l, t_VECSMALL);
     705       92340 :   for (j = 1; j < l; ++j)
     706             :   {
     707       83652 :     p3[j] = coset[p[mael(gen,j,1)]];
     708       83652 :     if (p3[j]==0) pari_err_IMPL("quotient_perm for a non-WSS group");
     709             :   }
     710        8688 :   return p3;
     711             : }
     712             : 
     713             : /* H is a subgroup of G, C is the quotient map G --> G/H
     714             :  *
     715             :  * Lift a subgroup S of G/H to a subgroup of G containing H */
     716             : GEN
     717       22626 : quotient_subgroup_lift(GEN C, GEN H, GEN S)
     718             : {
     719       22626 :   GEN genH = grp_get_gen(H);
     720       22626 :   GEN genS = grp_get_gen(S);
     721       22626 :   GEN genC = quo_get_gen(C);
     722       22626 :   long l1 = lg(genH)-1;
     723       22626 :   long l2 = lg(genS)-1, j;
     724       22626 :   GEN p1 = cgetg(3, t_VEC), L = cgetg(l1+l2+1, t_VEC);
     725       22626 :   for (j = 1; j <= l1; ++j) gel(L,j) = gel(genH,j);
     726       22626 :   for (j = 1; j <= l2; ++j) gel(L,l1+j) = gel(genC, mael(genS,j,1));
     727       22626 :   gel(p1,1) = L;
     728       22626 :   gel(p1,2) = vecsmall_concat(grp_get_ord(H), grp_get_ord(S));
     729       22626 :   return p1;
     730             : }
     731             : 
     732             : /* Let G a group and C a quotient map G --> G/H
     733             :  * Assume H is normal, return the group G/H */
     734             : GEN
     735        3312 : quotient_group(GEN C, GEN G)
     736             : {
     737        3312 :   pari_sp ltop = avma;
     738             :   GEN Qgen, Qord, Qelt, Qset, Q;
     739        3312 :   GEN Cgen = quo_get_gen(C);
     740        3312 :   GEN Ggen = grp_get_gen(G);
     741        3312 :   long i,j, n = lg(Cgen)-1, l = lg(Ggen);
     742        3312 :   Qord = cgetg(l, t_VECSMALL);
     743        3312 :   Qgen = cgetg(l, t_VEC);
     744        3312 :   Qelt = mkvec(identity_perm(n));
     745        3312 :   Qset = groupelts_set(Qelt, n);
     746       12000 :   for (i = 1, j = 1; i < l; ++i)
     747             :   {
     748        8688 :     GEN  g = quotient_perm(C, gel(Ggen,i));
     749        8688 :     long o = perm_relorder(g, Qset);
     750        8688 :     gel(Qgen,j) = g;
     751        8688 :     Qord[j] = o;
     752        8688 :     if (o != 1)
     753             :     {
     754        5940 :       Qelt = perm_generate(g, Qelt, o);
     755        5940 :       Qset = groupelts_set(Qelt, n);
     756        5940 :       j++;
     757             :     }
     758             :   }
     759        3312 :   setlg(Qgen,j);
     760        3312 :   setlg(Qord,j); Q = mkvec2(Qgen, Qord);
     761        3312 :   return gerepilecopy(ltop,Q);
     762             : }
     763             : 
     764             : /* Return 1 if g normalizes N, 0 otherwise */
     765             : long
     766       49242 : group_perm_normalize(GEN N, GEN g)
     767             : {
     768       49242 :   pari_sp ltop = avma;
     769       49242 :   long r = gequal(vecvecsmall_sort(group_leftcoset(N, g)),
     770             :                   vecvecsmall_sort(group_rightcoset(N, g)));
     771       49242 :   avma = ltop; return r;
     772             : }
     773             : 
     774             : /* L is a list of subgroups, C is a coset and r a relative order.*/
     775             : static GEN
     776       36594 : liftlistsubgroups(GEN L, GEN C, long r)
     777             : {
     778       36594 :   pari_sp ltop = avma;
     779       36594 :   long c = lg(C)-1, l = lg(L)-1, n = lg(gel(C,1))-1, i, k;
     780             :   GEN R;
     781       36594 :   if (!l) return cgetg(1,t_VEC);
     782       30306 :   R = cgetg(l*c+1, t_VEC);
     783       73152 :   for (i = 1, k = 1; i <= l; ++i)
     784             :   {
     785       42846 :     GEN S = gel(L,i), Selt = group_set(S,n);
     786       42846 :     GEN gen = grp_get_gen(S);
     787       42846 :     GEN ord = grp_get_ord(S);
     788             :     long j;
     789      129948 :     for (j = 1; j <= c; ++j)
     790             :     {
     791       87102 :       GEN p = gel(C,j);
     792       87102 :       if (perm_relorder(p, Selt) == r && group_perm_normalize(S, p))
     793       47352 :         gel(R,k++) = mkvec2(vec_append(gen, p),
     794             :                             vecsmall_append(ord, r));
     795             :     }
     796             :   }
     797       30306 :   setlg(R, k);
     798       30306 :   return gerepilecopy(ltop, R);
     799             : }
     800             : 
     801             : /* H is a normal subgroup, C is the quotient map G -->G/H,
     802             :  * S is a subgroup of G/H, and G is embedded in Sym(l)
     803             :  * Return all the subgroups K of G such that
     804             :  * S= K mod H and K inter H={1} */
     805             : static GEN
     806       22626 : liftsubgroup(GEN C, GEN H, GEN S)
     807             : {
     808       22626 :   pari_sp ltop = avma;
     809       22626 :   GEN V = trivialsubgroups();
     810       22626 :   GEN Sgen = grp_get_gen(S);
     811       22626 :   GEN Sord = grp_get_ord(S);
     812       22626 :   GEN Cgen = quo_get_gen(C);
     813       22626 :   long n = lg(Sgen), i;
     814       59220 :   for (i = 1; i < n; ++i)
     815             :   { /*loop over generators of S*/
     816       36594 :     GEN W = group_leftcoset(H, gel(Cgen, mael(Sgen, i, 1)));
     817       36594 :     V = liftlistsubgroups(V, W, Sord[i]);
     818             :   }
     819       22626 :   return gerepilecopy(ltop,V);
     820             : }
     821             : 
     822             : /* 1:A4 2:S4 0: other */
     823             : long
     824        3162 : group_isA4S4(GEN G)
     825             : {
     826        3162 :   GEN elt = grp_get_gen(G);
     827        3162 :   GEN ord = grp_get_ord(G);
     828        3162 :   long n = lg(ord);
     829        3162 :   if (n != 4 && n != 5) return 0;
     830        1098 :   if (ord[1]!=2 || ord[2]!=2 || ord[3]!=3) return 0;
     831          12 :   if (perm_commute(gel(elt,1),gel(elt,3))) return 0;
     832          12 :   if (n==4) return 1;
     833           6 :   if (ord[4]!=2) return 0;
     834           6 :   if (perm_commute(gel(elt,3),gel(elt,4))) return 0;
     835           6 :   return 2;
     836             : }
     837             : /* compute all the subgroups of a group G */
     838             : GEN
     839        3840 : group_subgroups(GEN G)
     840             : {
     841        3840 :   pari_sp ltop = avma;
     842             :   GEN p1, H, C, Q, M, sg1, sg2, sg3;
     843        3840 :   GEN gen = grp_get_gen(G);
     844        3840 :   GEN ord = grp_get_ord(G);
     845        3840 :   long lM, i, j, n = lg(gen);
     846        3840 :   if (n == 1) return trivialsubgroups();
     847        3162 :   if (group_isA4S4(G))
     848             :   {
     849          12 :     GEN s = gel(gen,1);       /*s = (1,2)(3,4) */
     850          12 :     GEN t = gel(gen,2);       /*t = (1,3)(2,4) */
     851          12 :     GEN st = perm_mul(s, t); /*st = (1,4)(2,3) */
     852          12 :     H = dicyclicgroup(s, t, 2, 2);
     853             :     /* sg3 is the list of subgroups intersecting only partially with H*/
     854          12 :     sg3 = cgetg((n==4)?4: 10, t_VEC);
     855          12 :     gel(sg3,1) = cyclicgroup(s, 2);
     856          12 :     gel(sg3,2) = cyclicgroup(t, 2);
     857          12 :     gel(sg3,3) = cyclicgroup(st, 2);
     858          12 :     if (n==5)
     859             :     {
     860           6 :       GEN u = gel(gen,3);
     861           6 :       GEN v = gel(gen,4), w, u2;
     862           6 :       if (zv_equal(perm_conj(u,s), t)) /*u=(2,3,4)*/
     863           6 :         u2 = perm_mul(u,u);
     864             :       else
     865             :       {
     866           0 :         u2 = u;
     867           0 :         u = perm_mul(u,u);
     868             :       }
     869           6 :       if (perm_order(v)==2)
     870             :       {
     871           6 :         if (!perm_commute(s,v)) /*v=(1,2)*/
     872             :         {
     873           0 :           v = perm_conj(u,v);
     874           0 :           if (!perm_commute(s,v)) v = perm_conj(u,v);
     875             :         }
     876           6 :         w = perm_mul(v,t); /*w=(1,4,2,3)*/
     877             :       }
     878             :       else
     879             :       {
     880           0 :         w = v;
     881           0 :         if (!zv_equal(perm_mul(w,w), s)) /*w=(1,4,2,3)*/
     882             :         {
     883           0 :           w = perm_conj(u,w);
     884           0 :           if (!zv_equal(perm_mul(w,w), s)) w = perm_conj(u,w);
     885             :         }
     886           0 :         v = perm_mul(w,t); /*v=(1,2)*/
     887             :       }
     888           6 :       gel(sg3,4) = dicyclicgroup(s,v,2,2);
     889           6 :       gel(sg3,5) = dicyclicgroup(t,perm_conj(u,v),2,2);
     890           6 :       gel(sg3,6) = dicyclicgroup(st,perm_conj(u2,v),2,2);
     891           6 :       gel(sg3,7) = dicyclicgroup(s,w,2,2);
     892           6 :       gel(sg3,8) = dicyclicgroup(t,perm_conj(u,w),2,2);
     893           6 :       gel(sg3,9) = dicyclicgroup(st,perm_conj(u2,w),2,2);
     894             :     }
     895             :   }
     896             :   else
     897             :   {
     898        3150 :     long osig = mael(factoru(ord[1]), 1, 1);
     899        3150 :     GEN sig = perm_pow(gel(gen,1), ord[1]/osig);
     900        3150 :     H = cyclicgroup(sig,osig);
     901        3150 :     sg3 = NULL;
     902             :   }
     903        3162 :   C = group_quotient(G,H);
     904        3156 :   Q = quotient_group(C,G);
     905        3156 :   M = group_subgroups(Q); lM = lg(M);
     906             :   /* sg1 is the list of subgroups containing H*/
     907        3150 :   sg1 = cgetg(lM, t_VEC);
     908        3150 :   for (i = 1; i < lM; ++i) gel(sg1,i) = quotient_subgroup_lift(C,H,gel(M,i));
     909             :   /*sg2 is a list of lists of subgroups not intersecting with H*/
     910        3150 :   sg2 = cgetg(lM, t_VEC);
     911             :   /* Loop over all subgroups of G/H */
     912        3150 :   for (j = 1; j < lM; ++j) gel(sg2,j) = liftsubgroup(C, H, gel(M,j));
     913        3150 :   p1 = gconcat(sg1, shallowconcat1(sg2));
     914        3150 :   if (sg3)
     915             :   {
     916          12 :     p1 = gconcat(p1, sg3);
     917          12 :     if (n==5) /*ensure that the D4 subgroups of S4 are in supersolvable format*/
     918          24 :       for(j = 3; j <= 5; j++)
     919             :       {
     920          18 :         GEN c = gmael(p1,j,1);
     921          18 :         if (!perm_commute(gel(c,1),gel(c,3)))
     922             :         {
     923          12 :           if (perm_commute(gel(c,2),gel(c,3))) { swap(gel(c,1), gel(c,2)); }
     924             :           else
     925           6 :             perm_mul_inplace2(gel(c,2), gel(c,1));
     926             :         }
     927             :       }
     928             :   }
     929        3150 :   return gerepileupto(ltop,p1);
     930             : }
     931             : 
     932             : /*return 1 if G is abelian, else 0*/
     933             : long
     934         780 : group_isabelian(GEN G)
     935             : {
     936         780 :   GEN g = grp_get_gen(G);
     937         780 :   long i, j, n = lg(g);
     938        1254 :   for(i=2; i<n; i++)
     939        1284 :     for(j=1; j<i; j++)
     940         810 :       if (!perm_commute(gel(g,i), gel(g,j))) return 0;
     941         654 :   return 1;
     942             : }
     943             : 
     944             : /*If G is abelian, return its HNF matrix*/
     945             : GEN
     946         282 : group_abelianHNF(GEN G, GEN S)
     947             : {
     948         282 :   GEN M, g = grp_get_gen(G), o = grp_get_ord(G);
     949         282 :   long i, j, k, n = lg(g);
     950         282 :   if (!group_isabelian(G)) return NULL;
     951         222 :   if (n==1) return cgetg(1,t_MAT);
     952         210 :   if (!S) S = group_elts(G, group_domain(G));
     953         210 :   M = cgetg(n,t_MAT);
     954         744 :   for(i=1; i<n; i++)
     955             :   {
     956         534 :     GEN P, C = cgetg(n,t_COL);
     957         534 :     pari_sp av = avma;
     958         534 :     gel(M,i) = C;
     959         534 :     P = perm_pow(gel(g,i), o[i]);
     960         774 :     for(j=1; j<lg(S); j++)
     961         774 :       if (zv_equal(P, gel(S,j))) break;
     962         534 :     avma = av;
     963         534 :     if (j==lg(S)) pari_err_BUG("galoisisabelian [inconsistent group]");
     964         534 :     j--;
     965         996 :     for(k=1; k<i; k++)
     966             :     {
     967         462 :       long q = j / o[k];
     968         462 :       gel(C,k) = stoi(j - q*o[k]);
     969         462 :       j = q;
     970             :     }
     971         534 :     gel(C,k) = stoi(o[i]);
     972         534 :     for (k++; k<n; k++) gel(C,k) = gen_0;
     973             :   }
     974         210 :   return M;
     975             : }
     976             : 
     977             : /*If G is abelian, return its abstract SNF matrix*/
     978             : GEN
     979         240 : group_abelianSNF(GEN G, GEN L)
     980             : {
     981         240 :   pari_sp ltop = avma;
     982         240 :   GEN H = group_abelianHNF(G,L);
     983         240 :   if (!H) return NULL;
     984         180 :   return gerepileupto(ltop, smithclean( ZM_snf(H) ));
     985             : }
     986             : 
     987             : GEN
     988         144 : abelian_group(GEN v)
     989             : {
     990         144 :   long card = zv_prod(v), i, d = 1, l = lg(v);
     991         144 :   GEN G = cgetg(3,t_VEC), gen = cgetg(l,t_VEC);
     992         144 :   gel(G,1) = gen;
     993         144 :   gel(G,2) = vecsmall_copy(v);
     994         324 :   for(i=1; i<l; i++)
     995             :   {
     996         180 :     GEN p = cgetg(card+1, t_VECSMALL);
     997         180 :     long o = v[i], u = d*(o-1), j, k, l;
     998         180 :     gel(gen, i) = p;
     999             :     /* The following loop is over-optimized. Remember that I wrote it for
    1000             :      * testpermutation. Something has survived... BA */
    1001         654 :     for(j=1;j<=card;)
    1002             :     {
    1003        1320 :       for(k=1;k<o;k++)
    1004        1026 :         for(l=1;l<=d; l++,j++) p[j] = j+d;
    1005         294 :       for (l=1; l<=d; l++,j++) p[j] = j-u;
    1006             :     }
    1007         180 :     d += u;
    1008             :   }
    1009         144 :   return G;
    1010             : }
    1011             : 
    1012             : /*return 1 if H is a normal subgroup of G*/
    1013             : long
    1014          48 : group_subgroup_isnormal(GEN G, GEN H)
    1015             : {
    1016          48 :   GEN g = grp_get_gen(G);
    1017          48 :   long i, n = lg(g);
    1018          48 :   if (lg(grp_get_gen(H)) > 1 && group_domain(G) != group_domain(H))
    1019           0 :     pari_err_DOMAIN("group_subgroup_isnormal","domain(H)","!=",
    1020             :                     strtoGENstr("domain(G)"), H);
    1021         108 :   for(i=1; i<n; i++)
    1022          78 :     if (!group_perm_normalize(H, gel(g,i))) return 0;
    1023          30 :   return 1;
    1024             : }
    1025             : 
    1026             : long
    1027         252 : groupelts_exponent(GEN elts)
    1028             : {
    1029         252 :   long i, n = lg(elts)-1, expo = 1;
    1030        3054 :   for(i=1; i<=n; i++)
    1031        2802 :     expo = clcm(expo, perm_order(gel(elts,i)));
    1032         252 :   return expo;
    1033             : }
    1034             : 
    1035             : GEN
    1036         594 : groupelts_center(GEN S)
    1037             : {
    1038         594 :   pari_sp ltop = avma;
    1039         594 :   long i, j, n = lg(S)-1, l = n;
    1040         594 :   GEN V, elts = zero_F2v(n+1);
    1041       21402 :   for(i=1; i<=n; i++)
    1042             :   {
    1043       20808 :     if (F2v_coeff(elts,i)) { l--;  continue; }
    1044      467910 :     for(j=1; j<=n; j++)
    1045      459192 :       if (!perm_commute(gel(S,i),gel(S,j)))
    1046             :       {
    1047       11646 :         F2v_set(elts,i);
    1048       11646 :         F2v_set(elts,j); l--; break;
    1049             :       }
    1050             :   }
    1051         594 :   V = cgetg(l+1,t_VEC);
    1052       21402 :   for (i=1, j=1; i<=n ;i++)
    1053       20808 :     if (!F2v_coeff(elts,i)) gel(V,j++) = vecsmall_copy(gel(S,i));
    1054         594 :   return gerepileupto(ltop,V);
    1055             : }
    1056             : 
    1057             : GEN
    1058         852 : groupelts_conjclasses(GEN elts, long *ptnbcl)
    1059             : {
    1060         852 :   long i, j, cl = 0, n = lg(elts)-1;
    1061         852 :   GEN c = const_vecsmall(n,0);
    1062       17484 :   for (i=1; i<=n; i++)
    1063             :   {
    1064       16632 :     GEN g = gel(elts,i);
    1065       16632 :     if (c[i]) continue;
    1066        7200 :     c[i] = ++cl;
    1067      182868 :     for(j=1; j<=n; j++)
    1068             :     {
    1069      175668 :       GEN h = perm_conj(gel(elts,j), g);
    1070      175668 :       long i2 = vecsearch(elts,h,NULL);
    1071      175668 :       c[i2] = cl;
    1072             :     }
    1073             :   }
    1074         852 :   if (ptnbcl) *ptnbcl = cl;
    1075         852 :   return c;
    1076             : }
    1077             : 
    1078             : /* S a list of generators */
    1079             : GEN
    1080           0 : groupelts_abelian_group(GEN S)
    1081             : {
    1082           0 :   pari_sp ltop = avma;
    1083             :   GEN Qgen, Qord, Qelt;
    1084           0 :   long i, j, n = lg(gel(S,1))-1, l = lg(S);
    1085           0 :   Qord = cgetg(l, t_VECSMALL);
    1086           0 :   Qgen = cgetg(l, t_VEC);
    1087           0 :   Qelt = mkvec(identity_perm(n));
    1088           0 :   for (i = 1, j = 1; i < l; ++i)
    1089             :   {
    1090           0 :     GEN  g = gel(S,i);
    1091           0 :     long o = perm_relorder(g, groupelts_set(Qelt, n));
    1092           0 :     gel(Qgen,j) = g;
    1093           0 :     Qord[j] = o;
    1094           0 :     if (o != 1) { Qelt = perm_generate(g, Qelt, o); j++; }
    1095             :   }
    1096           0 :   setlg(Qgen,j);
    1097           0 :   setlg(Qord,j);
    1098           0 :   return gerepilecopy(ltop, mkvec2(Qgen, Qord));
    1099             : }
    1100             : 
    1101             : GEN
    1102          12 : group_export_GAP(GEN G)
    1103             : {
    1104          12 :   pari_sp av = avma;
    1105          12 :   GEN s, comma, g = grp_get_gen(G);
    1106          12 :   long i, k, l = lg(g);
    1107          12 :   if (l == 1) return strtoGENstr("Group(())");
    1108           6 :   s = cgetg(2*l, t_VEC);
    1109           6 :   comma = strtoGENstr(", ");
    1110           6 :   gel(s,1) = strtoGENstr("Group(");
    1111          24 :   for (i=1, k=2; i < l; ++i)
    1112             :   {
    1113          18 :     if (i > 1) gel(s,k++) = comma;
    1114          18 :     gel(s,k++) = perm_to_GAP(gel(g,i));
    1115             :   }
    1116           6 :   gel(s,k++) = strtoGENstr(")");
    1117           6 :   return gerepilecopy(av, shallowconcat1(s));
    1118             : }
    1119             : 
    1120             : GEN
    1121          12 : group_export_MAGMA(GEN G)
    1122             : {
    1123          12 :   pari_sp av = avma;
    1124          12 :   GEN s, comma, g = grp_get_gen(G);
    1125          12 :   long i, k, l = lg(g);
    1126          12 :   if (l == 1) return strtoGENstr("PermutationGroup<1|>");
    1127           6 :   s = cgetg(2*l, t_VEC);
    1128           6 :   comma = strtoGENstr(", ");
    1129           6 :   gel(s,1) = gsprintf("PermutationGroup<%ld|",group_domain(G));
    1130          24 :   for (i=1, k=2; i < l; ++i)
    1131             :   {
    1132          18 :     if (i > 1) gel(s,k++) = comma;
    1133          18 :     gel(s,k++) = GENtoGENstr( vecsmall_to_vec(gel(g,i)) );
    1134             :   }
    1135           6 :   gel(s,k++) = strtoGENstr(">");
    1136           6 :   return gerepilecopy(av, shallowconcat1(s));
    1137             : }
    1138             : 
    1139             : GEN
    1140          24 : group_export(GEN G, long format)
    1141             : {
    1142          24 :   switch(format)
    1143             :   {
    1144          12 :   case 0: return group_export_GAP(G);
    1145          12 :   case 1: return group_export_MAGMA(G);
    1146             :   }
    1147           0 :   pari_err_FLAG("galoisexport");
    1148           0 :   return NULL; /*-Wall*/
    1149             : }

Generated by: LCOV version 1.11