README

To use reg_awk_permutation_groups.c, you need
(1) awkperm 
(2) reg_awk_permutation_groups.c

Here,
----- awkperm contains the regular pattern,
as well as the awk script to recognize good
permutations.
----- reg_awk_permutation_groups.c is C source code, which
uses a "system("awkperm")"
call to test if a permutation is good.

Additionally, "start_time" and "stop_time" are kept for
statistics. These can be removed, or are overwritten.


--------------------------------------


nawk ' # awkperm
BEGIN 	{  ok = 1 }
$1 ~ /^(ab)*$/  && $2 !~ /^(ab)*$/	{  ok = 0; exit }
END  {  exit(ok)  }' permutation_out



--------------------------------------


/****************************************************

	Program: reg_awk_permutation_groups.c
		 @copyright  1993  by Peter Clote
		  NSF grant CCR-9408090

	Computes the invariance groups of regular languages.
	Uses: awkfile "awkperm".

****************************************************/

#include <stdio.h>

typedef int *Array;
FILE *out;

main(int argc, char *argv[])
{
    int i,j,n,m,num=0;
    long pow, power(int,int);
    long fact,factorial(int);
    void nextvector(Array,int,int);
    void print(Array,int), println(Array,int);
    void printword(Array,int), printwordln(Array,int);
    void fprintword(Array,int), fprintwordln(Array,int);
    void next(Array,int);
    void permute(Array, Array, Array, int);
    Array a,x,y;

    if ( argc != 2 && argc != 3 )
        {
        fprintf(stderr,"Usage: %s num [num].\n",argv[0]);
        exit(1);
        }
    n = atoi(argv[1]); 
    if ( argc != 2 )
        m = atoi(argv[2]);  	/* SIGMA is { 0,...,m-1 }  */
    else
        m = 2; 			/* SIGMA is { 0,1 }  */
    fact = factorial(n);
    a = ( Array ) calloc(n,sizeof(int));
    for (i=0;i<n;++i) a[i] = i;  /* a is ID permutation */
    x = ( Array ) calloc(n,sizeof(int));/* later set to 0 vector */
    y = ( Array ) calloc(n,sizeof(int));/* later set to sigma of x */
    for (i=0;i<fact;++i)
         {
         for (j=0;j<n;++j) x[j] = 0; /* x is 0 vector */
         pow = power(m,n);
         out = fopen("permutation_out","w"); /* prepare out file */
         for (j=0;j<pow;++j)
            {
            fprintword(x,n);
            fprintf(out," ");
            permute(a,x,y,n);
            fprintwordln(y,n);
            nextvector(x,n,m);
            }
         fclose(out);		/* reset out file */
         if ( system("awkperm") ) 
            {
            num++;
            printf("%d.\t",num);
            println(a,n); 	/* if awkperm = 1 then sigma good */
            }
         next(a,n);
         }
    system("rm -f permutation_out"); 
}

void permute(Array a, Array x, Array y, int n)
{
    int i;

    for (i=0; i<n; ++i)
        y[i] = x[a[i]];
    return;
}

void println(Array a, int n)
{
    int i;
    for (i=0;i<n;++i) printf(" %d",a[i]);
    printf("\n");
}

void print(Array a, int n)
{
    int i;
    for (i=0;i<n;++i) printf(" %d",a[i]);
}

void printwordln(Array a, int n)
{
    int i;
    for (i=0;i<n;++i) printf("%c",a[i]+'a');
    printf("\n");
}

void printword(Array a, int n)
{
    int i;
    for (i=0;i<n;++i) printf("%c",a[i]+'a');
}

void fprintwordln(Array a, int n)
{
    int i;
    for (i=0;i<n;++i) fprintf(out,"%c",a[i]+'a');
    fprintf(out,"\n");
}

void fprintword(Array a, int n)
{
    int i;
    for (i=0;i<n;++i) fprintf(out,"%c",a[i]+'a');
}


int power(int a,int b)
/* -----------------------------------------------
        compute a^b, for a,b > 0
----------------------------------------------- */
{ 
    int i,prod;

    if (a <= 0 || b <= 0) return -1;
    if (b == 1) return a;
    prod = a;
    for (i = 2; i <= b; ++i)  prod *= a;
    return prod;
}

void nextvector(Array x, int n, int m)
/* -----------------------------------------------
   Generates the next largest vector in lexicographic
   order, where parameter x[] is assumed to be a vector of 
   length n with coordinates among 0,...,m-1. 
----------------------------------------------- */
{

    int i, carry = 1;
    for (i=n-1; i>=0; --i)
        {
        x[i]++;
        carry = 0;
        if ( x[i] == m )
            {
            x[i] = 0;
            carry = 1;
            }
        if ( carry == 0 ) return; 
        }
}






int factorial(int n)
{
    int i,prod;

    if (n<0) return -1;
    if (n == 0 || n == 1) return 1;
    prod = 1;
    for (i = 2; i <= n; ++i)  prod *= i;
    return prod;
}

void next(Array a, int n)
/* Generates the next largest permutation in lexicographic
   order, where parameter a[] is assumed to be a permutation
   NOT equal to {n-1, n-2,..., 0} */
{
    int j,k,r,s,temp;
    for (j=n-2;a[j]>a[j+1];j--);
    /* j is the largest subscript with a[j] < a[j+1] */
    for (k=n-1;a[j]>a[k];k--);
    /* a[k] is the smallest integer greater than a[j] to 
       right of a[j]  */ 
    temp = a[j]; a[j] = a[k]; a[k] = temp; 
    /* interchange a[j] and a[k] */
    r=n-1;s=j+1;
    while (r>s)
        {
         temp=a[r];a[r]=a[s];a[s]=temp;
         /* interchange a[r] and a[s] */
         r--;s++;
        }
    /* This puts the tail end of the permutation
       after the j-th position in increasing order. */
}

--------------------------------------



aaaaaa aaaaaa
aaaaab abaaaa
aaaaba aaabaa
aaaabb ababaa
aaabaa aabaaa
aaabab abbaaa
aaabba aabbaa
aaabbb abbbaa