Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
C++ and Maple
TM
Programs 419
vpatterns3()
{
int curword[3]; //subword of word[] currently being tested
int i1,i2,i3;
for(i3=0;i3<n-2;i3++){
curword[0]=word[i3];
for(i2=i3+1;i2<n-1;i2++){
curword[1]=word[i2];
if (testK(1,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[2]=word[i1];
if (!testK(2,curword,p))
return 0;
}}}
return 1;//no pattern
}
int vpatterns4()
{
int curword[4]; //subword of word[] currently being tested
int i1,i2,i3,i4;
for(i4=0;i4<n-3;i4++){
curword[0]=word[i4];
for(i3=i4+1;i3<n-2;i3++){
curword[1]=word[i3];
if (testK(1,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[2]=word[i2];
if (testK(2,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[3]=word[i1];
if (!testK(3,curword,p))
return 0;
}}}}
return 1;//no pattern
}
int vpatterns5()
{
int curword[5]; //subword of word[] currently being tested
int i1,i2,i3,i4,i5;
for(i5=0;i5<n-4;i5++){
curword[0]=word[i5];
for(i4=i5+1;i4<n-3;i4++){
curword[1]=word[i4];
if (testK(1,curword,p)) continue;
for(i3=i4+1;i3<n-2;i3++){
curword[2]=word[i3];
if (testK(2,curword,p)) continue;
© 2010 by Taylor and Francis Group, LLC
420 Combinatorics of Compositions and Words
for(i2=i3+1;i2<n-1;i2++){
curword[3]=word[i2];
if (testK(3,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[4]=word[i1];
if (!testK(4,curword,p))
return 0;
}}}}}
return 1;//no pattern
}
int vpatterns6()
{
int curword[6];
int i1,i2,i3,i4,i5,i6;
for(i6=0;i6<n-5;i6++){
curword[0]=word[i6];
for(i5=i6+1;i5<n-4;i5++){
curword[1]=word[i5];
if (testK(1,curword,p)) continue;
for(i4=i5+1;i4<n-3;i4++){
curword[2]=word[i4];
if (testK(2,curword,p)) continue;
for(i3=i4+1;i3<n-2;i3++){
curword[3]=word[i3];
if (testK(3,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[4]=word[i2];
if (testK(4,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[5]=word[i1];
if (!testK(5,curword,p))
return 0;
}}}}}}
return 1;
}
int vpatterns7()
{
int curword[7];
int i1,i2,i3,i4,i5,i6,i7;
for(i7=0;i7<n-6;i7++){
curword[0]=word[i7];
for(i6=i7+1;i6<n-5;i6++){
curword[1]=word[i6];
if (testK(1,curword,p)) continue;
for(i5=i6+1;i5<n-4;i5++){
curword[2]=word[i5];
if (testK(2,curword,p)) continue;
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 421
for(i4=i5+1;i4<n-3;i4++){
curword[3]=word[i4];
if (testK(3,curword,p)) continue;
for(i3=i4+1;i3<n-2;i3++){
curword[4]=word[i3];
if (testK(4,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[5]=word[i2];
if (testK(5,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[6]=word[i1];
if (!testK(6,curword,p))
return 0;
}}}}}}}
return 1;
}
void builtwords(int l,int lenp)
{
int j;
if (l==n)
{
if(lenp==3){
numberword=numberword+vpatterns3();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==4){
numberword=numberword+vpatterns4();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==5){
numberword=numberword+vpatterns5();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==6){
numberword=numberword+vpatterns6();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==7){
numberword=numberword+vpatterns7();
if (numberword==10000000) {num2++; numberword=0;}
}
}
else
for(j=0;j<NK;j++){
word[l]=j; builtwords(l+1,lenp);
}
}
© 2010 by Taylor and Francis Group, LLC
422 Combinatorics of Compositions and Words
void main()
{
int i,lenp;
printf("Please enter the length of the subsequence
pattern (3-7): ");
scanf("%d",&lenp);
printf("Please enter the pattern : ");
for(i=0;i<lenp;i++) scanf("%d",&p[i]);
/*output file*/
fout=fopen("data.dat","w");
printf("Please enter the number of letters in your alphabet, k=");
scanf("%d",&NK);
for(n=1;n<10;n++) /*the length n*/
{
for(i=0;i<n;i++) word[i]=0;
builtwords(0,lenp);
printf("The number of words in [%d]^%d that avoid the
pattern is 10^7*%d+%d \n",NK,n,num2,numberword);
fprintf(fout,"The number of words in [%d]^%d that avoid the
pattern is 10^7*%d+%d \n",NK,n,num2,numberword);
}
fclose(fout);
}
G.4 Program to compute AW
τ
[k]
(n) for all subsequence pat-
terns
τ of fixed length
This is the program for words that corresponds to the one in Section G.2
for compositions. For words, there are two additional routines that check
whether the complement and the reversal of the complement of the current
pattern is already in the list, namely compl1 and reversalcompl.
#include <stdio.h>
#define MAXN 40
int n,NK;
int word[MAXN],p[MAXN], numdp;
long numberword=0,num2=0;
int listp[100000][10],nlistp=0;
FILE *fout;
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 423
int order(int a,int b)
{ if (a==b) return 0; else if(a>b) return 1; else return -1; }
int testK(int k,int *p1,int *p2)
{
int i;
for (i=0;i<k;i++)
if (order(p1[i],p1[k])!=order(p2[i],p2[k])) return 1;
return 0;
}
vpatterns3()
{
int curword[3]; //subword of word[] currently being tested
int i1,i2,i3;
for(i3=0;i3<n-2;i3++){
curword[0]=word[i3];
for(i2=i3+1;i2<n-1;i2++){
curword[1]=word[i2];
if (testK(1,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[2]=word[i1];
if (!testK(2,curword,p))
return 0;
}}}
return 1;//no pattern
}
int vpatterns4()
{
int curword[4]; //subword of word[] currently being tested
int i1,i2,i3,i4;
for(i4=0;i4<n-3;i4++){
curword[0]=word[i4];
for(i3=i4+1;i3<n-2;i3++){
curword[1]=word[i3];
if (testK(1,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[2]=word[i2];
if (testK(2,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[3]=word[i1];
if (!testK(3,curword,p))
return 0;
}}}}
return 1;//no pattern
}
© 2010 by Taylor and Francis Group, LLC
424 Combinatorics of Compositions and Words
int vpatterns5()
{
int curword[5]; //subword of word[] currently being tested
int i1,i2,i3,i4,i5;
for(i5=0;i5<n-4;i5++){
curword[0]=word[i5];
for(i4=i5+1;i4<n-3;i4++){
curword[1]=word[i4];
if (testK(1,curword,p)) continue;
for(i3=i4+1;i3<n-2;i3++){
curword[2]=word[i3];
if (testK(2,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[3]=word[i2];
if (testK(3,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[4]=word[i1];
if (!testK(4,curword,p))
return 0;
}}}}}
return 1;//no pattern
}
int vpatterns6()
{
int curword[6];
int i1,i2,i3,i4,i5,i6;
for(i6=0;i6<n-5;i6++){
curword[0]=word[i6];
for(i5=i6+1;i5<n-4;i5++){
curword[1]=word[i5];
if (testK(1,curword,p)) continue;
for(i4=i5+1;i4<n-3;i4++){
curword[2]=word[i4];
if (testK(2,curword,p)) continue;
for(i3=i4+1;i3<n-2;i3++){
curword[3]=word[i3];
if (testK(3,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[4]=word[i2];
if (testK(4,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[5]=word[i1];
if (!testK(5,curword,p))
return 0;
}}}}}}
return 1;
}
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 425
int vpatterns7()
{
int curword[7];
int i1,i2,i3,i4,i5,i6,i7;
for(i7=0;i7<n-6;i7++){
curword[0]=word[i7];
for(i6=i7+1;i6<n-5;i6++){
curword[1]=word[i6];
if (testK(1,curword,p)) continue;
for(i5=i6+1;i5<n-4;i5++){
curword[2]=word[i5];
if (testK(2,curword,p)) continue;
for(i4=i5+1;i4<n-3;i4++){
curword[3]=word[i4];
if (testK(3,curword,p)) continue;
for(i3=i4+1;i3<n-2;i3++){
curword[4]=word[i3];
if (testK(4,curword,p)) continue;
for(i2=i3+1;i2<n-1;i2++){
curword[5]=word[i2];
if (testK(5,curword,p)) continue;
for(i1=i2+1;i1<n;i1++){
curword[6]=word[i1];
if (!testK(6,curword,p))
return 0;
}}}}}}}
return 1;
}
void builtwords(int l,int lenp)
{
int j;
if (l==n)
{
if(lenp==3){
numberword=numberword+vpatterns3();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==4){
numberword=numberword+vpatterns4();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==5){
numberword=numberword+vpatterns5();
if (numberword==10000000) {num2++; numberword=0;}
}
if(lenp==6){
numberword=numberword+vpatterns6();
if (numberword==10000000) {num2++; numberword=0;}
© 2010 by Taylor and Francis Group, LLC
426 Combinatorics of Compositions and Words
}
if(lenp==7){
numberword=numberword+vpatterns7();
if (numberword==10000000) {num2++; numberword=0;}
}
}
else
for(j=0;j<NK;j++){
word[l]=j; builtwords(l+1,lenp);
}
}
int isword(int lenp)
{
int i,j,m,fg;
m=0;
for(i=0;i<lenp;i++) if(m<p[i]) m=p[i];
for(i=1;i<=m;i++){
fg=1;
for(j=0;j<lenp;j++) if (p[j]==i) fg=0;
if(fg==1) return(0);
}
return(1);
}
int reversal(int lenp)
{
int i,j,fg;
for(i=0;i<nlistp;i++){
fg=1;
for(j=0;j<lenp;j++)
if (listp[i][j]!=p[lenp-1-j]) fg=0;
if (fg==1) return(0);
}
return(1);
}
/* check whether the complement of p is already in list */
int compl1(int lenp)
{
int i,j,fg,m;
m=0;
for(i=0;i<lenp;i++)
if (m<p[i]) m=p[i];
for(i=0;i<nlistp;i++){
fg=1;
for(j=0;j<lenp;j++)
if(listp[i][j]!=(m+1-p[j])) fg=0;
if (fg==1) return(0);
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 427
}
return(1);
}
/* check whether the reverse of the complement of p */
/* is already in list */
int reversalcompl(int lenp)
{
int i,j,fg,m;
m=0;
for(i=0;i<lenp;i++)
if (m<p[i]) m=p[i];
for(i=0;i<nlistp;i++){
fg=1;
for(j=0;j<lenp;j++)
if(listp[i][j]!=(m+1-p[lenp-1-j])) fg=0;
if (fg==1) return(0);
}
return(1);
}
int checkp(int lenp)
{
if (isword(lenp)==0) return(0);
if (reversal(lenp)==0) return(0);
if (compl1(lenp)==0) return(0);
if (reversalcompl(lenp)==0) return(0);
return(1);
}
void builtpatterns(int l,int lenp)
{
int i,j;
if (l==lenp)
{
if (checkp(lenp)==1)
{
for(i=0;i<lenp;i++) listp[nlistp][i]=p[i];
nlistp++;
numdp=0;
for(i=0;i<lenp;i++) if (numdp<p[i]) numdp=p[i];
NK=numdp+2;
printf("%5d) pattern=",nlistp);
fprintf(fout,"%5d) pattern=",nlistp);
for(i=0;i<lenp;i++) printf("%d",p[i]);
printf(" :\n");
for(i=0;i<lenp;i++) fprintf(fout,"%d",p[i]);
fprintf(fout," :\n");
© 2010 by Taylor and Francis Group, LLC
428 Combinatorics of Compositions and Words
for(n=1;n<11;n++){
numberword=0; num2=0;
for(i=0;i<n;i++) word[i]=0;
builtwords(0,lenp);
printf("The number of words in [%d]^%d that avoid the
pattern is 10^7*%d+%d\n",NK,n,num2,numberword);
fprintf(fout,"The number of words in [%d]^%d that avoid the
pattern is 10^7*%d+%d\n",NK,n,num2,numberword);
}
printf("\n");
fprintf(fout,"\n");
}
}
else
for(j=1;j<=lenp;j++){
p[l]=j; builtpatterns(l+1,lenp);
}
}
void main()
{
int lenp=3; /* length of the subsequence patterns */
fout=fopen("data.dat","w");
builtpatterns(0,lenp);
fclose(fout);
}
We have listed the nontrivial Wilf-equivalence classes for subsequence pat-
terns of length four and five for words in Tables 6.3 and 6.4. Propositions 6.18
and 6.19 together with Theorem 6.20 completely classify the Wilf-equivalence
classes for these patterns. Tables G.3 and G.4 contain all Wilf-equivalence
classes, including the ones that consist of a single pattern. Due to the much
larger number of words of length n (as opposed to compositions of n), we
present the values AW
τ
[5]
(n)forn =4,...,9andAW
τ
[6]
(n)forn =5, 6,...,9,
respectively. If these values do not distinguish between two patterns, then we
provide values obtained using the above program for larger n from a conve-
nient alphabet to show that the patterns are indeed in different classes.
TABLE G.3: Subsequence patterns of length four
τ The sequence {|AW
τ
[5]
(n)|}
9
n=4
|AW
τ
[6]
(9)|
1111 620, 3020, 14300, 65100, 281400, 1138200
1112,1121 615, 2935, 13425, 58259, 237798, 906722
1122 615, 2915, 13095, 55235, 217710, 799910
1123,1132 615, 2935, 13475, 59319, 250306, 1013790
© 2010 by Taylor and Francis Group, LLC