Heubach S., Mansour T. Combinatorics of Compositions and Words

Подождите немного. Документ загружается.

C++ and Maple

Programs 429

τ The sequence {|AW

[5]

(n)|}

n=4

|AW

[6]

(9)|

1212 615, 2915, 13065, 54615, 211165, 752875

1213 615, 2935, 13469, 59215, 249298, 1006608

1221 615, 2915, 13075, 54815, 213180, 766450

1223,1232

1322,2132 615, 2935, 13469, 59209, 249173, 1005169 5149600

1332 615, 2935, 13469, 59209, 249173, 1005169 5149598

1231 615, 2935, 13470, 59225, 249319, 1006165

1234,1243

1432,2143 620, 3028, 14495, 67875, 310815, 1392795

1312 615, 2935, 13459, 59019, 247148, 989288

1324 620, 3028, 14495, 67876, 310839, 1393119

1342 620, 3028, 14494, 67854, 310563, 1390527

1423 620, 3028, 14494, 67853, 310540, 1390229

2413 620, 3028, 14493, 67830, 310245, 1387439

TABLE G.4: Subsequence patterns of length ﬁve

τ The sequence {|AW

[6]

(n)|}

n=5

|AW

[k]

(n)|

13132 7756 46066 269850 1549246 8668438

12313 7756 46066 269850 1549357 8672194

21312 7756 46066 269850 1549366 8672416

13212 7756 46066 269850 1549369 8672514

13213 7756 46066 269850 1549387 8673242

12312 7756 46066 269865 1549822 8680105

12132 7756 46066 269865 1549846 8680923

12123 7756 46066 269865 1549846 8680947 |[6]

(τ)| =47240506

13232 7756 46066 269865 1549846 8680947 |[6]

(τ)| =47240485

13312 7756 46066 269880 1550224 8685684

21132 7756 46066 269880 1550269 8687310

12231 7756 46066 269880 1550281 8687574

13122 7756 46066 269880 1550281 8687576

12213 7756 46066 269880 1550293 8688164

12332 7756 46066 269880 1550314 8688780

12321 7756 46066 269880 1550326 8689188

13231 7756 46066 269880 1550326 8689200

12331 7756 46066 269880 1550338 8689424

13322 7756 46066 269910 1551280 8705626

11223,11232

11322 7756 46066 269910 1551322 8707026 |[5]

(τ)| =32695299

11332 7756 46066 269910 1551322 8707026 |[5]

(τ)| =32695309

11323 7756 46066 269910 1551322 8707110

11233 7756 46066 269910 1551406 8709812

12112 7761 46191 271601 1566981 8808636

11212 7761 46191 271601 1567021 8810056 |[4]

(τ)| =630518

12121 7761 46191 271601 1567021 8810056 |[4]

(τ)| =630510

12221 7761 46191 271601 1567061 8811456

11221 7761 46191 271641 1568381 8835086

11122 7761 46191 271641 1568501 8839406

13112 7756 46096 270720 1563457 8839536

11312 7756 46096 270720 1563478 8840287

12131 7756 46096 270720 1563508 8841205

12223,12232

12322,13222

430 Combinatorics of Compositions and Words

τ The sequence {|AW

[6]

(n)|}

n=5

|AW

[k]

(n)|

21232,21322 7756 46096 270720 1563556 8842756

13332 7756 46096 270720 1563577 8843421

12113 7756 46096 270720 1563577 8843505

11213 7756 46096 270720 1563598 8844100

11231 7756 46096 270741 1564146 8852076

11321 7756 46096 270741 1564161 8852553

11123,11132 7756 46096 270741 1564221 8854416

11112,11121

11211 7761 46231 272831 1588265 9080246

24213 7761 46227 272775 1588571 9102298

21413 7761 46227 272775 1588594 9102967

23413 7761 46227 272775 1588606 9103392

13142 7761 46227 272775 1588612 9103499

14213 7761 46227 272775 1588621 9103889

21423 7761 46227 272775 1588626 9104029

12423 7761 46227 272775 1588626 9104030

13242 7761 46227 272775 1588626 9104042

14243 7761 46227 272775 1588626 9104049

12413 7761 46227 272775 1588630 9104200

13124 7761 46227 272775 1588644 9104648

14312 7761 46227 272782 1588798 9106336

13412 7761 46227 272782 1588802 9106427

23142 7761 46227 272781 1588793 9106631

14132 7761 46227 272782 1588812 9106775

14123 7761 46227 272782 1588833 9107422

21342 7761 46227 272782 1588843 9107811

24113 7761 46227 272787 1588964 9109294

22413 7761 46227 272787 1588979 9109802

14223 7761 46227 272787 1588985 9110008

13342 7761 46227 272787 1588985 9110048

13442 7761 46227 272787 1589003 9110617

14233 7761 46227 272787 1589003 9110623

14332 7761 46227 272787 1589006 9110734

14232 7761 46227 272787 1589006 9110739

13432 7761 46227 272787 1589006 9110755

14323 7761 46227 272787 1589006 9110764

13423 7761 46227 272787 1589006 9110775

21432 7761 46227 272788 1589026 9110925

12342 7761 46227 272788 1589027 9110961

14342 7761 46227 272787 1589013 9110997

13224 7761 46227 272787 1589013 9111007

13241 7761 46227 272789 1589046 9111087

12431 7761 46227 272789 1589050 9111199

12314 7761 46227 272788 1589034 9111208

13243 7761 46227 272787 1589020 9111228

12324 7761 46227 272787 1589020 9111229

12432 7761 46227 272788 1589041 9111413

13214 7761 46227 272788 1589048 9111684

13422 7761 46227 272794 1589198 9113691

14423 7761 46227 272794 1589205 9113892

14322 7761 46227 272794 1589219 9114366

12341 7761 46227 272795 1589241 9114562

14432 7761 46227 272794 1589226 9114595

12234,12243

12343,12433

21243,21433 7761 46227 272794 1589226 9114597 |[6]

(τ)| =51363833

C++ and Maple

Programs 431

τ The sequence {|AW

[6]

(n)|}

n=5

|AW

[k]

(n)|

12443,21143 7761 46227 272794 1589226 9114597 |[6]

(τ)| =51363835

12134,12143 7761 46227 272794 1589233 9114853

11423 7761 46227 272801 1589429 9117845

11342 7761 46227 272801 1589429 9117873

11234,11243

11432 7761 46227 272801 1589457 9118797

11324 7761 46227 272801 1589457 9118829

11111 7770 46470 276570 1633170 9536520

24153 7770 46480 276920 1640192 9642494

25314 7770 46480 276920 1640195 9642602

24513 7770 46480 276921 1640225 9643100

25413 7770 46480 276921 1640227 9643168

14253 7770 46480 276921 1640228 9643213

23514 7770 46480 276921 1640228 9643215

13524 7770 46480 276921 1640232 9643365

25143 7770 46480 276922 1640262 9643856

13542 7770 46480 276922 1640264 9643933

15324 7770 46480 276922 1640264 9643936

15243 7770 46480 276922 1640265 9643969

14352 7770 46480 276922 1640265 9643973

13425 7770 46480 276922 1640267 9644046

14523 7770 46480 276923 1640296 9644505

13452 7770 46480 276923 1640297 9644543

15423 7770 46480 276923 1640297 9644545

15234 7770 46480 276923 1640298 9644578

12534,21534 7770 46480 276923 1640298 9644582

15342 7770 46480 276923 1640298 9644583

12453,21453 7770 46480 276923 1640299 9644620

14532 7770 46480 276923 1640300 9644655

12345,12354

12543,15432

21354,21543 7770 46480 276924 1640334 9645304

12435,13254 7770 46480 276924 1640335 9645343

14325 7770 46480 276924 1640335 9645344

G.5 Programs TOU AUTO and TOU FORMULA

We now present the programs that were mentioned in Subsection 7.3.1. The

C++ program TOU

AUTO has as input the alphabet and the subsequence

pattern to be avoided, and returns the states of the automaton for pattern

avoidance in words and the associated transfer matrix. The Maple program

TOU

FORMULA takes as input the transfer matrix from the C++ program

and returns the ﬁrst terms of the sequence {AW

[k]

(n)}, as well as an explicit

formula for AW

[k]

(n).

432 Combinatorics of Compositions and Words

G.5.1 C++ program TOU AUTO

#include <stdio.h>

/* maximal number of states of the automaton */

#define MAXCLASSES 2000

/* MAXBIN=max(# of states, k+1) */

#define MAXBIN 2000

/* maximal length of state name */

#define MAXLCLASS 20

/* each pattern consists of exactly one row and at most 20 columns */

#define MAXROWS 1

#define MAXCOLS 20

/* number of letters k in the alphabet */

int NUMBERLETTER;

/* list of all the possible extensions for a state needed to */

/* check equivalence (see Lemma 7.27) */

int mat[MAXBIN][MAXROWS][MAXCOLS];

/* length of the extensions in mat[MAXBIN] */

int lmat[MAXBIN];

/* number of all the possible extensions listed in mat[MAXBIN]*/

int nallmat;

int pattern[MAXROWS][MAXCOLS]; /* pattern to be avoided */

int numbercolumn,numberrow,lenpattern; /* lenpattern=3,4,5,6*/

/* three different states and their respective length */

int state0[MAXROWS][MAXLCLASS], lstate0;

int state1[MAXROWS][MAXLCLASS], lstate1;

int state2[MAXROWS][MAXLCLASS], lstate2;

/* the transfer matrix Au(p,k) and its dimension */

int Au[MAXCLASSES][MAXCLASSES], sizeAu=0;

/* the set E(p,k) of equivalence classes for a given pattern p */

int setclass[MAXCLASSES][MAXROWS][MAXLCLASS];

/* length of a state in E(p,k) */

int lsetclass[MAXCLASSES];

/* cardinality of |E(p,k)| */

int nclass;

C++ and Maple

Programs 433

/* output file */

FILE *fout;

/* builds all the possible extensions for a state for the given */

/* alphabet, that is, the list of words r in Lemma 7.27 */

void extendbymat()

{

int nc,i,j,i1,j1,ii,nu;

nallmat=0;

for(nc=1;nc<1+numbercolumn;nc++)

{

nu=1;

for(i=0;i<nc*(numberrow);i++) nu=nu*NUMBERLETTER;

lmat[nallmat]=nc;

for(i=0;i<numberrow;i++)

for(j=0;j<nc;j++) mat[nallmat][i][j]=0;

nallmat++;

for(ii=0;ii<nu-1;ii++)

{

for(i=0;i<numberrow;i++)

for(j=0;j<nc;j++)

mat[nallmat][i][j]=mat[nallmat-1][i][j];

i=0; j=0;

while(mat[nallmat][i][j]==(NUMBERLETTER-1))

{i++; if(i==numberrow) {j++; i=0;} }

mat[nallmat][i][j]++;

for(j1=0;j1<j;j1++)

for(i1=0;i1<numberrow;i1++) mat[nallmat][i1][j1]=0;

for(i1=0;i1<i;i1++)

mat[nallmat][i1][j]=0;

lmat[nallmat]=nc; nallmat++;

}

int ordereq(int a, int b)

{ if(a<b) return(1); else if(a>b) return(-1); else return(0); }

/* check if two sequences of length 3 are order-isomorphic*/

int equiv3(int a, int b, int c,

int a1, int b1, int c1)

{

int i,v[3],u[3];

v[0]=ordereq(a,b); v[1]=ordereq(a,c); v[2]=ordereq(b,c);

u[0]=ordereq(a1,b1);u[1]=ordereq(a1,c1);u[2]=ordereq(b1,c1);

for(i=0;i<3;i++)

if(v[i]!=u[i]) return(0);

return(1);

}

434 Combinatorics of Compositions and Words

/* check if two sequences of length 4 are order-isomorphic*/

int equiv4(int a, int b, int c, int d,

int a1, int b1, int c1, int d1)

{

int i,v[6],u[6];

v[0]=ordereq(a,b); v[1]=ordereq(a,c); v[2]=ordereq(a,d);

v[3]=ordereq(b,c); v[4]=ordereq(b,d); v[5]=ordereq(c,d);

u[0]=ordereq(a1,b1);u[1]=ordereq(a1,c1);u[2]=ordereq(a1,d1);

u[3]=ordereq(b1,c1);u[4]=ordereq(b1,d1);u[5]=ordereq(c1,d1);

for(i=0;i<6;i++)

if(v[i]!=u[i]) return(0);

return(1);

}

/* check if two sequences of length 5 are order-isomorphic*/

int equiv5(int a, int b, int c, int d, int e,

int a1, int b1, int c1, int d1,int e1)

{

int i,v[10],u[10];

v[0]=ordereq(a,b); v[1]=ordereq(a,c); v[2]=ordereq(a,d);

v[3]=ordereq(a,e); v[4]=ordereq(b,c); v[5]=ordereq(b,d);

v[6]=ordereq(b,e); v[7]=ordereq(c,d); v[8]=ordereq(c,e);

v[9]=ordereq(d,e);

u[0]=ordereq(a1,b1);u[1]=ordereq(a1,c1);u[2]=ordereq(a1,d1);

u[3]=ordereq(a1,e1);u[4]=ordereq(b1,c1);u[5]=ordereq(b1,d1);

u[6]=ordereq(b1,e1);u[7]=ordereq(c1,d1);u[8]=ordereq(c1,e1);

u[9]=ordereq(d1,e1);

for(i=0;i<10;i++)

if(v[i]!=u[i]) return(0);

return(1);

}

/* check if two sequences of length 6 are order-isomorphic*/

int equiv6(int a, int b, int c, int d, int e,int f,

int a1, int b1, int c1, int d1,int e1,int f1)

{

int i,v[10],u[10];

v[0]=ordereq(a,b); v[1]=ordereq(a,c); v[2]=ordereq(a,d);

v[3]=ordereq(a,e); v[4]=ordereq(a,f); v[5]=ordereq(b,c);

v[6]=ordereq(b,d); v[7]=ordereq(b,e); v[8]=ordereq(b,f);

v[9]=ordereq(c,d); v[10]=ordereq(c,e); v[11]=ordereq(c,f);

v[12]=ordereq(d,e); v[13]=ordereq(d,f); v[14]=ordereq(e,f);

u[0]=ordereq(a1,b1); u[1]=ordereq(a1,c1); u[2]=ordereq(a1,d1);

u[3]=ordereq(a1,e1); u[4]=ordereq(a1,f1); u[5]=ordereq(b1,c1);

u[6]=ordereq(b1,d1); u[7]=ordereq(b1,e1); u[8]=ordereq(b1,f1);

u[9]=ordereq(c1,d1); u[10]=ordereq(c1,e1);u[11]=ordereq(c1,f1);

u[12]=ordereq(d1,e1);u[13]=ordereq(d1,f1);u[14]=ordereq(e1,f1);

for(i=0;i<15;i++)

C++ and Maple

Programs 435

if(v[i]!=u[i]) return(0);

return(1);

}

/* check if state0 avoids pattern of length 3 */

int avoid3()

{

int i1,i2,i3;

for(i1=0;i1<lstate0-2;i1++)

for(i2=i1+1;i2<lstate0-1;i2++)

for(i3=i2+1;i3<lstate0;i3++)

if(equiv3(state0[0][i1],state0[0][i2],state0[0][i3],

pattern[0][0],pattern[0][1],pattern[0][2])==1)

return(0);

return(1);

}

/* check if state0 avoids pattern of length 4 */

int avoid4()

{

int i1,i2,i3,i4;

for(i1=0;i1<lstate0-3;i1++)

for(i2=i1+1;i2<lstate0-2;i2++)

for(i3=i2+1;i3<lstate0-1;i3++)

for(i4=i3+1;i4<lstate0;i4++)

if(equiv4(state0[0][i1],state0[0][i2],state0[0][i3],state0[0][i4],

pattern[0][0],pattern[0][1],pattern[0][2],pattern[0][3])==1)

return(0);

return(1);

}

/* check if state0 avoids pattern of length 5 */

int avoid5()

{

int i1,i2,i3,i4,i5;

for(i1=0;i1<lstate0-4;i1++)

for(i2=i1+1;i2<lstate0-3;i2++)

for(i3=i2+1;i3<lstate0-2;i3++)

for(i4=i3+1;i4<lstate0-1;i4++)

for(i5=i4+1;i5<lstate0;i5++)

if(equiv5(state0[0][i1],state0[0][i2],state0[0][i3],

state0[0][i4],state0[0][i5],pattern[0][0],pattern[0][1],

pattern[0][2],pattern[0][3],pattern[0][4])==1)

return(0);

return(1);

}

/* check if state0 avoids pattern of length 6 */

int avoid6()

436 Combinatorics of Compositions and Words

{

int i1,i2,i3,i4,i5,i6;

for(i1=0;i1<lstate0-5;i1++)

for(i2=i1+1;i2<lstate0-4;i2++)

for(i3=i2+1;i3<lstate0-3;i3++)

for(i4=i3+1;i4<lstate0-2;i4++)

for(i5=i4+1;i5<lstate0-1;i5++)

for(i6=i5+1;i6<lstate0;i6++)

if(equiv6(state0[0][i1],state0[0][i2],state0[0][i3],

state0[0][i4],state0[0][i5],state0[0][i6],pattern[0][0],

pattern[0][1],pattern[0][2],pattern[0][3],pattern[0][4],

pattern[0][5])==1) return(0);

return(1);

}

/* check if a pattern of length lenpattern is avoided */

int avoiding()

{

if (lenpattern==3) return(avoid3());

if (lenpattern==4) return(avoid4());

if (lenpattern==5) return(avoid5());

if (lenpattern==6) return(avoid6());

return(-1);

}

/* check if state1 and state2 are equivalent */

int equivstates()

{

int i,j,i1,j1,ans1,ans2;

int statea[MAXROWS][MAXLCLASS], lstatea,

stateb[MAXROWS][MAXLCLASS], lstateb;

lstate0=lstate1; lstatea=lstate1;

for(i=0;i<numberrow;i++)

for(j=0;j<lstate1;j++)

{

state0[i][j]=state1[i][j];

statea[i][j]=state1[i][j];

}

ans1=avoiding(); /* check if state1 avoids pattern */

lstate0=lstate2; lstateb=lstate2;

for(i=0;i<numberrow;i++)

for(j=0;j<lstate2;j++)

{

state0[i][j]=state2[i][j];

stateb[i][j]=state2[i][j];

}

ans2=avoiding(); /* check if state2 avoids pattern */

if(ans1!=ans2) return(0); /* not equivalent since one state */

/* avoids p and the other does not */

C++ and Maple

Programs 437

for(j=0;j<nallmat;j++)

{

lstatea=lstate1; lstateb=lstate2;

for(i1=0;i1<numberrow;i1++)

for(j1=0;j1<lmat[j];j1++)

{

statea[i1][j1+lstatea]=mat[j][i1][j1];

stateb[i1][j1+lstateb]=mat[j][i1][j1];

}

lstatea=lstate1+lmat[j];

lstateb=lstate2+lmat[j];

lstate0=lstatea;

for(i1=0;i1<numberrow;i1++)

for(j1=0;j1<lstatea;j1++) state0[i1][j1]=statea[i1][j1];

ans1=avoiding();

lstate0=lstateb;

for(i1=0;i1<numberrow;i1++)

for(j1=0;j1<lstateb;j1++) state0[i1][j1]=stateb[i1][j1];

ans2=avoiding();

if(ans1!=ans2) return(0);

}

return(1);

}

/* check if there is a state in E(p,k) that is */

/* equivalent to an already existing state (state1) */

int checkequivstates()

{

int i,i1,j1,ans;

for(i=0;i<nclass;i++)

{

lstate2=lsetclass[i];

for(i1=0;i1<numberrow;i1++)

for(j1=0;j1<lstate2;j1++) state2[i1][j1]=setclass[i][i1][j1];

ans=equivstates();

if (ans==1) return(i);

}

return(nclass);

}

/* transfer matrix Au(p,k) and set of classes in E(p,k) */

void automat()

{

int i,j,flag=1,nst=1,

i1,j1,ans,pns,

ans1,numvec;

numvec=1;

for(i=0;i<numberrow;i++) numvec=numvec*NUMBERLETTER;

438 Combinatorics of Compositions and Words

/* first state, the empty state */

lsetclass[0]=0; nclass=1;

printf("%d) empty state\n",nclass);

fprintf(fout,"%d) empty state\n",nclass);

sizeAu=1; Au[0][0]=0;

pns=1;

/* find another state, if there is one */

while(flag==1)

{

flag=0;

for(i=nst-1;i<pns;i++)

{

lstate1=lsetclass[i]; /* take old state */

for(i1=0;i1<numberrow;i1++)

for(j1=0;j1<lstate1;j1++)

state1[i1][j1]=setclass[i][i1][j1];

lstate1++; /* extend the state in all possible ways */

for(j=0;j<numvec;j++)

{

for(i1=0;i1<numberrow;i1++)

state1[i1][lstate1-1]=mat[j][i1][0];

ans=checkequivstates(); /* check after the extension if */

/* there is an old state equivalent to it */

if (ans==nclass) /* if not */

{

lstate0=lstate1; /*check if state is avoiding the pattern */

for(i1=0;i1<numberrow;i1++)

for(j1=0;j1<lstate0;j1++)

state0[i1][j1]=state1[i1][j1];

ans1=avoiding();

if(ans1==1) /* if the new state avoids the pattern */

{

/* put it as a new state in E(p,k) */

/* and extend the transfer matrix */

flag=1;

printf("%d) ",nclass+1);

fprintf(fout,"%d) ",nclass+1);

for(i1=0;i1<numberrow;i1++)

{

for(j1=0;j1<lstate1;j1++)