Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
Appendix G
C++ and Maple
TM
Programs
Sections G.1 through G.4 contain C++ programs to count the number of
compositions and words, respectively, that avoid either a single pattern en-
tered by the user or all subsequence patterns τ of a fixed length. Section
G.5 contains a C++ and a Maple program. The C++ program TOU
AUTO
computes the states and the transfer matrix of the automaton for avoidance of
subsequence patterns in words. The Maple program TOU
FORMULA com-
putes the first few values and an explicit formula for the sequence {AW
τ
[k]
(n)}
from the transfer matrix obtained as output of the C++ program. These pro-
grams, as well as Java versions of the programs in Sections G.1 and G.3 can be
downloaded from the author’s website http://math.haifa.ac.il/toufik/
manbook.html. The Java versions are provided for readers that do not have
access to a C++ compiler, but they are slower than the C++ versions and
are not suitable for massive computation.
G.1 Program to compute AC
τ
N
(n) for given τ
This program computes the number of compositions of n for n =1, 2,...,20
that avoid a pattern entered by the user. If the pattern is a subsequence
pattern of length three, four, five, or six then the functions vpatterns3(),
vpatterns4(), vpatterns5(),andvpatterns6() are to be used. For a sub-
word pattern of length dp the relevant function is swpatterns(dp), while for
generalized patterns of length four we use gpatterns112(), gpatterns121(),
and gpatterns22(dp). Note that the routine gpatterns22 is more general as
it enumerates the compositions that avoid the generalized pattern (dp − 2, 2)
for dp ≥ 4. The routine gpatterns22(dp) illustrates how the user might
modify the other routines for generalized patterns of length four to deal with
generalized patterns of length greater than four. The program also contains
two routines that check whether a pattern occurs: testK for subsequence
patterns and testW for the other two types of patterns.
The routine builtcomps recursively creates all compositions of n and in-
creases the count if the composition avoids the pattern p. The user can adjust
the type of patterns for which the program checks by making the relevant
399
© 2010 by Taylor and Francis Group, LLC
400 Combinatorics of Compositions and Words
routines active. As presented below, the program checks for subsequence pat-
terns. The user is prompted for the length of the pattern and the specific
pattern to be checked. After the computation the output is presented on the
screen and also written into a file named data.dat.
#include <stdio.h>
#define MAXN 40 /*max number of parts in the composition*/
int n; /* composition of n*/
int comp[MAXN], /* composition */
p[MAXN], /* pattern */
lcomp; /* number of parts of comp */
long numbercomp=0;
/*number of compositions of n that avoid the pattern p */
FILE *fout; /*output file */
/* comparison between two elements */
int order(int a,int b)
{
if (a==b) return 0; else if(a>b) return 1; else return -1;
}
/* testing whether two sequences are order-isomorphic */
/* k = length of sequences */
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;
}
int testW(int k,int * p1,int * p2)
{
int i,j;
for (i=0;i<k-1;i++)
for(j=i+1;j<k;j++)
if (order(p1[i],p1[j])!=order(p2[i],p2[j])) return 1;
return 0;
}
/* check whether comp avoids subsequence pattern p of length 3 */
int vpatterns3()
{
int curword[3]; //subword of comp[] currently being tested
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 401
int nn=lcomp;
int i1,i2,i3;
for(i3=0;i3<nn-2;i3++){
curword[0]=comp[i3];
for(i2=i3+1;i2<nn-1;i2++){
curword[1]=comp[i2];
if (testK(1,curword,p)) continue;
for(i1=i2+1;i1<nn;i1++){
curword[2]=comp[i1];
if (!testK(2,curword,p))
return 0;
}}}
return 1;//no pattern
}
/* check whether comp avoids subsequence pattern p of length 4 */
int vpatterns4() {
int curword[4]; //subword of comp[] currently being tested
int nn=lcomp;
int i1,i2,i3,i4;
for(i4=0;i4<nn-3;i4++){
curword[0]=comp[i4];
for(i3=i4+1;i3<nn-2;i3++){
curword[1]=comp[i3];
if (testK(1,curword,p)) continue;
for(i2=i3+1;i2<nn-1;i2++){
curword[2]=comp[i2];
if (testK(2,curword,p)) continue;
for(i1=i2+1;i1<nn;i1++){
curword[3]=comp[i1];
if (!testK(3,curword,p)
return 0;
}}}}
return 1;//no pattern
}
/* check whether comp avoids subsequence pattern p of length 5 */
int vpatterns5() {
int curword[5]; //subword of comp[] currently being tested
int nn=lcomp;
int i1,i2,i3,i4,i5;
for(i5=0;i5<nn-4;i5++){
curword[0]=comp[i5];
for(i4=i5+1;i4<nn-3;i4++){
curword[1]=comp[i4];
if (testK(1,curword,p)) continue;
for(i3=i4+1;i3<nn-2;i3++){
curword[2]=comp[i3];
if (testK(2,curword,p)) continue;
© 2010 by Taylor and Francis Group, LLC
402 Combinatorics of Compositions and Words
for(i2=i3+1;i2<nn-1;i2++){
curword[3]=comp[i2];
if (testK(3,curword,p)) continue;
for(i1=i2+1;i1<nn;i1++){
curword[4]=comp[i1];
if (!testK(4,curword,p))
return 0;
}}}}}
return 1;//no pattern
}
/* check whether comp avoids subsequence pattern p of length 6 */
int vpatterns6() {
int curword[6]; //subword of comp[] currently being tested
int nn=lcomp;
int i1,i2,i3,i4,i5,i6;
for(i6=0;i6<nn-5;i6++){
curword[0]=comp[i6];
for(i5=i6+1;i5<nn-4;i5++){
curword[1]=comp[i5];
if (testK(1,curword,p)) continue;
for(i4=i5+1;i4<nn-3;i4++){
curword[2]=comp[i4];
if (testK(2,curword,p)) continue;
for(i3=i4+1;i3<nn-2;i3++){
curword[3]=comp[i3];
if (testK(3,curword,p)) continue;
for(i2=i3+1;i2<nn-1;i2++){
curword[4]=comp[i2];
if (testK(4,curword,p)) continue;
for(i1=i2+1;i1<nn;i1++){
curword[5]=comp[i1];
if (!testK(5,curword,p))
return 0;
}}}}}}
return 1;//no pattern
}
/* check whether comp avoids subword pattern p of length dp */
int swpatterns(int dp) {
int curword[10]; //subword of comp[] currently being tested
int nn=lcomp,j,i1;
for(i1=0;i1<nn+1-dp;i1++)
{
for(j=0;j<dp;j++) curword[j]=comp[i1+j];
if (!testW(dp,curword,p)) return 0;
}
return 1;//no pattern
}
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 403
/* check whether comp avoids the pattern p of type (1,1,2) */
int gpatterns112() {
int curword[10]; //subword of comp[] currently being tested
int nn=lcomp,i1,i2,i3;
for(i1=0;i1<nn-3;i1++)
for(i2=i1+1;i2<nn-2;i2++)
for(i3=i2+1;i3<nn-1;i3++)
{
curword[0]=comp[i1]; curword[1]=comp[i2];
curword[2]=comp[i3]; curword[3]=comp[i3+1];
if (!testW(4,curword,p)) return 0;
}
return 1;//no pattern
}
/* check whether comp avoids the pattern p of type (1,2,1) */
int gpatterns121() {
int curword[10]; //subword of comp[] currently being tested
int nn=lcomp;
int i1,i2,i3,i4;
for(i1=0;i1<nn-3;i1++)
for(i2=i1+1;i2<nn-2;i2++)
{
i3=i2+1;
for(i4=i3+1;i4<nn;i4++)
{
curword[0]=comp[i1]; curword[1]=comp[i2];
curword[2]=comp[i3]; curword[3]=comp[i4];
if (!testW(4,curword,p)) return 0;
}
}
return 1;//no pattern
}
/* check whether comp avoids the pattern p of type (2,2) */
int gpatterns22(int dp) {
int curword[10]; //subword of comp[] currently being tested
int nn=lcomp;
int j,i1,i2;
for(i1=0;i1<nn+1-dp;i1++)
for(i2=i1+dp-2;i2<nn-1;i2++)
{
for(j=0;j<dp-2;j++) curword[j]=comp[i1+j];
curword[dp-2]=comp[i2]; curword[dp-1]=comp[i2+1];
if (!testW(dp,curword,p)) return 0;
}
return 1;//no pattern
}
© 2010 by Taylor and Francis Group, LLC
404 Combinatorics of Compositions and Words
/* recursively generating all the compositions comp of n */
/* if comp avoids the pattern p then count it */
/* l = parts considered, nnn= weight of comp, lenp = length of p */
void builtcomps(int l,int nnn,int lenp) {
int j;
if (nnn==0)
{
lcomp=l;
/* subsequence */
if(lenp==3) numbercomp=numbercomp+vpatterns3();
if(lenp==4) numbercomp=numbercomp+vpatterns4();
if(lenp==5) numbercomp=numbercomp+vpatterns5();
if(lenp==6) numbercomp=numbercomp+vpatterns6();
/* generalized patterns */
//if (lenp==4) numbercomp=numbercomp+gpatterns112();
//if (lenp==4) numbercomp=numbercomp+gpatterns121();
//if (lenp==4) numbercomp=numbercomp+gpatterns22(4);
/* subword pattern of length dp */
//if (lenp==4) numbercomp=numbercomp+swpatterns(4);
}
else
for(j=1;j<=nnn;j++)
{ comp[l]=j; builtcomps(l+1,nnn-j,lenp); }
}
/* User inputs length and pattern */
void main() {
int i,lenp;
printf("Please enter the length of the
subsequence pattern (3-6): ");
scanf("%d",&lenp);
printf("Please enter the pattern: ");
for(i=0;i<lenp;i++) scanf("%d",&p[i]);
fout=fopen("data.dat","w");
fprintf(fout,"The number of compositions of n
that avoid the pattern ");
for(i=0;i<lenp;i++) fprintf(fout,"%d",p[i]);
fprintf(fout," is given by\n");
printf("The number of compositions of n
that avoid the pattern ");
for(i=0;i<lenp;i++) printf("%d",p[i]);
printf(" is given by\n");
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 405
for(n=1;n<21;n++)
{
numbercomp=0;
for(i=0;i<n;i++) comp[i]=0;
lcomp=0;
builtcomps(0,n,lenp);
printf("Number of compositions of %2d that
avoid the pattern is %d\n",n,numbercomp);
fprintf(fout,"Number of compositions of %2d that
avoid the pattern is %d\n",n,numbercomp);
}
fclose(fout);
}
We illustrate the use of the program for the pattern 132.
Example G.1 To compute the number of compositions of n that avoid the
subsequence pattern τ = 132 for n =1, 2,...,20,weenter3 at the first
prompt, and 132(with spaces between the numbers) at the second prompt.
For subsequence patterns, the length can be between 3 and 6.
Please enter the length of the subsequence pattern (3-6): 3
Please enter the pattern: 1 3 2
The resulting output is
The number of compositions of n that avoid the pattern 132 is given
by
Number of compositions of 1 that avoid the pattern is 1
Number of compositions of 2 that avoid the pattern is 2
Number of compositions of 3 that avoid the pattern is 4
Number of compositions of 4 that avoid the pattern is 8
Number of compositions of 5 that avoid the pattern is 16
Number of compositions of 6 that avoid the pattern is 31
Number of compositions of 7 that avoid the pattern is 60
Number of compositions of 8 that avoid the pattern is 114
Number of compositions of 9 that avoid the pattern is 214
Number of compositions of 10 that avoid the pattern is 398
Number of compositions of 11 that avoid the pattern is 732
Number of compositions of 12 that avoid the pattern is 1334
Number of compositions of 13 that avoid the pattern is 2410
Number of compositions of 14 that avoid the pattern is 4321
Number of compositions of 15 that avoid the pattern is 7688
Number of compositions of 16 that avoid the pattern is 13590
Number of compositions of 17 that avoid the pattern is 23869
Number of compositions of 18 that avoid the pattern is 41686
Number of compositions of 19 that avoid the pattern is 72405
Number of compositions of 20 that avoid the pattern is 125144
Press any key to continue
© 2010 by Taylor and Francis Group, LLC
406 Combinatorics of Compositions and Words
G.2 Program to compute AC
τ
N
(n) for all subsequence pat-
terns
τ of fixed length
Unlike the program given in Section G.1, the following program computes
the sequence AC
τ
N
(n)forall subsequence patterns τ of a fixed length, that
is, the program will create those patterns and then basically run the program
given in Section G.1. Note that the program below only contains routines
that pertain to subsequence patterns, but can easily be adjusted by utilizing
the routines for subword or generalized patterns of the program listed in
Section G.1.
The additional routines are isword, reversal,andbuiltpatterns.The
first one checks whether a word of length lenp is indeed a pattern, that is, in
reduced form, while the second one checks whether the reversal of the current
pattern has already been considered. The third function recursively builds
all words of length lenp, then checks that the current word is a new pattern.
If so, the pattern is added to the list and the program computes AC
τ
N
(n)for
n =1, 2,...,24. The output is once more printed to the screen and to a file
named data.dat.
#include <stdio.h>
#define MAXN 40
#define MAXP 10000
int n;
int comp[MAXN],p[MAXN],lcomp;
long numbercomp=0;
int listp[MAXP][MAXN], /*list containing the patterns p, one per row*/
nlistp=0;
FILE *fout;
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;
}
int vpatterns3()
{
int curword[3]; //subword of comp[] currently being tested
int nn=lcomp,i1,i2,i3;
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 407
for(i3=0;i3<nn-2;i3++){
curword[0]=comp[i3];
for(i2=i3+1;i2<nn-1;i2++){
curword[1]=comp[i2];
if (testK(1,curword,p)) continue;
for(i1=i2+1;i1<nn;i1++){
curword[2]=comp[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;
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++){
© 2010 by Taylor and Francis Group, LLC
408 Combinatorics of Compositions and Words
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;
}
void builtcomps(int l,int nnn,int lenp)
{
int j;
if (nnn==0){
lcomp=l;
if(lenp==3) numbercomp=numbercomp+vpatterns3();
if(lenp==4) numbercomp=numbercomp+vpatterns4();
if(lenp==5) numbercomp=numbercomp+vpatterns5();
if(lenp==6) numbercomp=numbercomp+vpatterns6();
}
else
for(j=1;j<=nnn;j++){
comp[l]=j; builtcomps(l+1,nnn-j,lenp);
}
}
© 2010 by Taylor and Francis Group, LLC