A continuación se presenta el programa de computación que calcula los ACLR para el
caso (4,h), cabe señalar que el mismo proceso puede ser adaptado para cualquier tipo de
ACLR(k,r) pues la forma de detección es la misma para todos los casos.
#include "stdio.h"
#include "stdlib.h"
#include "ctype.h"
#include "string.h"
#include "math.h"
/***** DEFINICION DE VALORES *****/
/*Numero de estados del ACL */
#define numestados 4
/*Longitud de la regla de evolucion */
#define longregla 16
/*Longitud del numero wolfram */
#define longcadena 8
/* Valor de producto L*R */
#define indice 4
/*Numero de iteraciones a realizar para buscar el cluster minimo */
#define numit 6
/*Numero total de permutaciones */
#define numper 24
/*Indice izquierdo a buscar */
#define izquierdo 2
/*Indice derecho a buscar */
#define derecho 2
/***** VARIABLES GLOBALES QUE EL PROGRAMA UTILIZA *****/
/*Permutaciones posibles para buscar el cluster minimo*/
int permutaciones[numper][numestados]={
{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1},
{1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
{2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},{2,3,0,1},{2,3,1,0},
{3,0,1,2},{3,0,2,1},{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}};
/*Matriz de evolucion del ACL */
int matriz[numestados][numestados];
/*Matriz de las coordenadas de elementos del ACL */
int coordenadas[numestados][numestados-1];
/*Matriz de rutas en el ACL */
int rutas[numestados][numestados];
/*Condicion de llenado para cada estado */
int cond;
/* Matrices auxiliares para obtener la conectividad de cada estado y el cluster minimo de
un ACLR */
int matrizb[numestados][numestados];
int matrizc[numestados][numestados];
int matrizd[numestados][numestados];
/*Arreglo que recibe el numero wolfram del ACL */
char numwolfram[longcadena];
/*Arreglo que guarda la regla de evolucion del ACL */
char reglaevolucion[longregla];
/*Valor del tamaço de vecindad de la regla inversa si el ACL es reversible */
int maxvecindad=2;
/*Guarda la permutacion a realizar en la matriz de evolucion para buscar el cluster
minimo*/
int permutacion[numestados];
/*Guarda los cambios de estados a realizar en la matriz de evolucion para buscar el
cluster minimo */
int estados[numestados];
/*Cadenas que almacenaran numeros wolfram para encontrar el cluster minimo */
char nw[longcadena];
char clustemp[longcadena];
char final[longcadena];
/*Guarda cuantos estados hay de un mismo valor por renglon o columna */
int estren,estcol;
/*Guarda que estados y que renglones se van a permutar */
int renglon[numestados];
/*Cuenta cuantas permutaciones tienen que hacerse para encontrar el cluster minimo */
int numedos;
/*Numero de clusters minimos encontrados y archivo para guardarlos */
int totalclusters;
FILE *hoja;
int clusters[20000][longcadena];
/*Total de ACLR generados por el proceso */
int total;
/*Variables para visualizar el progreso del calculo */
int porcentaje=0;
int valor;
/*Valores de los indices de Welch */
int R,L;
/*****DECLARACION DE LAS FUNCIONES DEL PROGRAMA*****/
void imprimiravance();
void inicio();
void borrar(int edo);
int lugar(int posicion);
void inicializar(int edo);
void llenado(int edo);
int incrementar(int edo,int posicion);
int actualizar(int edo);
int checarciclos(int edo);
void conectividad(int edo, int aux[numestados][numestados]);
void multiplo(int matrizb[numestados][numestados],
int matrizc[numestados][numestados]);
int obtenerindices(int matriz[numestados][numestados],int edo,int largo);
int checarindices(int matriz[numestados][numestados], int largo);
int reversible();
void wolfram(int matriz[numestados][numestados]);
void contarestados();
void encontrar(int matriz[numestados][numestados]);
void asignar(int ind, int array[numestados]);
void permutar(int array[numestados],int matriz[numestados][numestados]);
void cambioest();
void menor();
void cluster();
int lista();
void calculo(int edo);
/***** FUNCIONES DEL PROGRAMA *****/
/*Presentar resultados en pantalla */
void imprimiravance()
{
int i,j;
printf("
n");
for(i=0;i<numestados;i++)
{
for(j=0;j<numestados;j++)
printf("%3d",matriz[i][j]);
printf("
n");
}
printf("
nACLR(4,h): %s",nw);
printf("
nCluster del ACLR(4,h):
%s",final);
printf("
nTotal de clusters minimos
encontrados: %2d 
n",totalclusters);
}
/*Inicializar matriz de evolucion y sus coordenadas*/
void inicio()
{
int i,j;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
matriz[i][j]=-1;
for(i=0;i<numestados;i++)
matriz[i][i]=i;
for(i=0;i<numestados-1;i++)
coordenadas[0][i]=i+1;
}
/* Borrar elementos de la matriz de evolucion */
void borrar(int edo)
{
int i,j;
int v1;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
if(i!=j)
if(matriz[i][j]==edo)
matriz[i][j]=-1;
}
/*Checa si el lugar a ocupar en la matriz de evolucion esta disponible */
int lugar(int posicion)
{
int t1,t2;
t1=posicion/numestados;
t2=posicion-(t1*numestados);
return(matriz[t1][t2]);
}
/*Inicializa las coordenadas del estado siguiente si un estado paso las pruebas anteriores
*/
void inicializar(int edo)
{ int i,j;
int t1,t2;
for(i=0;i<numestados-1;i++)
for(j=0;j<(numestados*numestados);j++)
if(lugar(j)==-1)
{
t1=j/numestados;
t2=j-(t1*numestados);
matriz[t1][t2]=edo;
coordenadas[edo][i]=j;
break;
}
}
/*Pone en la matriz de evolucion los elementos del estado segun la matriz de coordenadas
*/
void llenado(int edo)
{
int i,t1,t2;
for(i=0;i<numestados-1;i++)
{
t1=coordenadas[edo][i]/numestados;
t2=coordenadas[edo][i]-(t1*numestados);
matriz[t1][t2]=edo;
}
}
/*Funcion que escoge que coordenada actualizar*/
int incrementar(int edo,int posicion)
{
int flag;
int valor,valor2;
int i;
int t1,t2;
for(i=posicion;i<=numestados-2;i++)
{
flag=0;
if(i>posicion)
coordenadas[edo][i]=valor2;
while(flag==0)
{
valor=(++coordenadas[edo][i]);
if(valor>=(numestados*numestados))
{
borrar(edo);
return -1;
}
t1=valor/numestados;
t2=valor-(t1*numestados);
if(matriz[t1][t2]==-1)
{
matriz[t1][t2]=edo;
flag=1;
}
}
valor2=valor;
}
borrar(edo);
return 0;
}
/*Actualiza las coordenadas del estado */
int actualizar(int edo)
{
int i;
for(i=numestados-2;i>=0;i--)
if(incrementar(edo,i)==0)
break;
if(i==-1)
return -1;
return 0;
}
/* Checar si hay ciclos de longitud 2 en la matriz de evolucion */
int checarciclos(int edo)
{
int i,j,k;
int ciclo;
int v1,v2,p;
/*Obtiene la localizacion de el edo en la matriz y maximiza esta posicion */
p=0;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
if(matriz[i][j]==edo)
{
rutas[edo][p]=((i*i*i)+(j*j*j));
p++;
}
/*Compara si en el mismo estado hay ciclos */
for(i=0;i<numestados;i++)
{
v1=rutas[edo][i];
if(i>0)
for(j=0;j<i;j++)
{
v2=rutas[edo][j];
if(v2==v1)
return -1;
}
}
/*controla estados anteriores */
for(i=0;i<edo;i++)
{
ciclo=0;
for(j=0;j<numestados;j++)
{
for(k=0;k< numestados;k++)
{
v1=rutas[i][k];
v2=rutas[edo][j];
if(v1==v2)
{
ciclo++;
if(ciclo>1)
return -1;
break;
}
}
}
}
return 0;
}
/*Obtiene la matriz de conectividad del ACL de un edo dado y la guarda en aux*/
void conectividad(int edo, int aux[numestados][numestados])
{
int i,j;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
aux[i][j]=0;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
if(matriz[i][j]==edo)
aux[i][j]=1;
}
/*Multiplica dos matrices dadas y guarda el resultado en matrizd*/
void multiplo(int matrizb[numestados][numestados], int matrizc[numestados][numestados])
{
int i,j,k;
int temp;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
{
temp=0;
for(k=0;k<numestados;k++)
temp+=matrizb[i][k]*matrizc[k][j];
matrizd[i][j]=temp;
}
}
/*Obtiene el valor de los indices de Welch para ver si el ACL es reversible*/
int obtenerindices(int matriz[numestados][numestados],int edo)
{
int i,j,k;
int valor;
int diagonal;
int matrizaux[numestados][numestados];
/*Copia la matriz de conectividad que recibe */
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
matrizaux[i][j]=matriz[i][j];
/*Multiplica la matriz de conectividad que recibe por la matriz de conectividad de el
estado 0 */
conectividad(edo,matrizc);
multiplo(matrizaux,matrizc);
/*Si la suma de elementos es diferente que el valor del "indice", no se cumple
con la multiplicidad uniforme */
valor=0;
for(j=0;j<numestados;j++)
for(k=0;k<numestados;k++)
valor+=matrizd[j][k];
if(valor!=indice)
{
/* No se cumple la Multiplicidad Uniforme */
return -1;
}
/*Para que el ACL sea reversible, debe haber un solo elemento en la diagonal principal y
L*R=k2r */
diagonal=0;
for(j=0;j<numestados;j++)
if(matrizd[j][j]!=0)
diagonal++;
if(diagonal>1)
{
/*Multiples Ancestros */
return -1;
}
/*Obtiene cuantos renglones cumplen con el valor del indice derecho*/
R=0;
for(j=0;j<numestados;j++)
{
valor=0;
for(k=0;k<numestados;k++)
if(matrizd[j][k]!=0)
valor++;
if(valor==derecho)
R++;
}
/*Obtiene cuantas columnas cumplen con el valor del indice izquierdo*/
L=0;
for(j=0;j<numestados;j++)
{
valor=0;
for(k=0;k<numestados;k++)
if(matrizd[k][j]!=0)
valor++;
if(valor==izquierdo)
L++;
}
/*Checa si los indices cumplen con L*R=k2r*/
valor=0;
if(((R*L)==indice)&&(diagonal==1))
valor=1;
if(valor==0)
{
valor=(obtenerindices(matrizd,edo));
if(valor==-1)
return -1;
}
return 0;
}
/*Recibe una matriz de conectividad, la multiplica las matrices de conectividad de cada
estado y verifica si L*R=k2r , en este caso, guarda en maxvecindad el numero de arcos de
la ruta para saber el valor de 2r+1 en la regla inversa */
int checarindices(int matriz[numestados][numestados])
{
int i,j,k;
int valor;
int diagonal;
int matrizaux[numestados][numestados];
/*Copia la matriz de conectividad que recibe */
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
matrizaux[i][j]=matriz[i][j];
/*Multiplica la matriz de conectividad que recibe por cada matriz de conectividad de los
demas estados */
for(i=0;i<numestados;i++)
{
conectividad(i,matrizc);
multiplo(matrizaux,matrizc);
/*Si la suma de elementos es diferente que el valor del "indice", no se cumple
con la multiplicidad uniforme */
valor=0;
for(j=0;j<numestados;j++)
for(k=0;k<numestados;k++)
valor+=matrizd[j][k];
if(valor!=indice)
{
/*No se cumple la Multiplicidad Uniforme*/
return -1;
}
/*Para que el ACL sea reversible, debe haber un solo elemento en la diagonal principal y
L*R=k2r */
diagonal=0;
for(j=0;j<numestados;j++)
if(matrizd[j][j]!=0)
diagonal++;
if(diagonal>1)
{
/*Multiples Ancestros*/
return -1;
}
/*Obtiene cuantos renglones cumplen con el valor del indice derecho*/
R=0;
for(j=0;j<numestados;j++)
{
valor=0;
for(k=0;k<numestados;k++)
if(matrizd[j][k]!=0)
valor++;
if(valor==derecho)
R++;
}
/*Obtiene cuantas columnas cumplen con el valor del indice izquierdo*/
L=0;
for(j=0;j<numestados;j++)
{
valor=0;
for(k=0;k<numestados;k++)
if(matrizd[k][j]!=0)
valor++;
if(valor==izquierdo)
L++;
}
/*Checa si los indices cumplen con L*R=k2r*/
valor=0;
if(((R*L)==indice)&&(diagonal==1))
valor=1;
/*Si no se cumple la condicion anterior se vuelve a hacer el proceso */
if(valor==0)
{
valor=(checarindices(matrizd,vecindad+1));
if(valor==-1)
return -1;
}
}
return 0;
}
/*Checa si el automata es reversible*/
int reversible()
{
int i;
for(i=0;i<numestados;i++)
{
conectividad(i,matrizb);
if((checarindices(matrizb,2))==-1)
return -1;
}
return 0;
}
/*Calcula el numero wolfram de una matriz de evolucion */
void wolfram(int matriz[numestados][numestados])
{
int i,j;
int temp=0;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
reglaevolucion[(i*numestados)+j]=matriz[i][j];
for(i=longcadena-1;i>=0;i--)
{
temp=(numestados*reglaevolucion[(i*2)+1])+reglaevolucion[(i*2)];
if(temp<10)
nw[longcadena-1-i]=toascii(48+temp);
else
nw[longcadena-1-i]=toascii(55+temp);
}
}
/*Busca si es necesario trasponer la matriz para encontrar el cluster minimo */
void contarestados()
{
int i,j;
int temp;
estren=estcol=0;
for(i=0;i<numestados;i++)
{
temp=0;
for(j=0;j<numestados;j++)
if(matriz[i][i]==matriz[i][j])
temp++;
if(temp>estren)
estren=temp;
}
for(i=0;i<numestados;i++)
{
temp=0;
for(j=0;j<numestados;j++)
if(matriz[i][i]==matriz[j][i])
temp++;
if(temp>estcol)
estcol=temp;
}
}
/*Encuentra que renglones tienen mas elementos de un mismo estado y guarda en arreglo
renglon esta informacion */
void encontrar(int matriz[numestados][numestados])
{
int i,j;
int temp,temp2,aux;
temp2=aux=0;
numedos=1;
renglon[aux]=0;
/*Encuentra que renglon tiene mas elementos de un mismo estado */
for(i=0;i<numestados;i++)
{
temp=0;
for(j=0;j<numestados;j++)
if(matriz[i][j]==matriz[i][i])
temp++;
if(temp>temp2)
{
temp2=temp;
renglon[aux]=i;
}
}
/*Encuentra si otros renglones tienen el mismo numero de elementos de un mismo estado */
for(i=0;i<numestados;i++)
{
temp=0;
if(i!=renglon[aux])
{
for(j=0;j<numestados;j++)
if(matriz[i][j]==matriz[i][i])
temp++;
if(temp==temp2)
{
renglon[numedos]=i;
numedos++;
}
}
}
}
/*Asigna a un arreglo la permutacion de la matriz permutaciones */
void asignar(int ind, int array[numestados])
{
int i;
for(i=0;i<numestados;i++)
array[i]=permutaciones[ind][i];
}
/*Permuta los renglones y las columnas de la matriz de evolucion y guarda esta en matrizb
*/
void permutar(int array[numestados],int matriz[numestados][numestados])
{
int i,j;
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
matrizc[i][j]=matriz[array[(numestados-1)-i]][array[(numestados-1)-j]];
}
/*Cambia los estados de la matriz de evolucion */
void cambioest()
{
int i,j,k;
int contador;
int temp;
contador=0;
for(i=numestados-1;i>=0;i--)
{
for(j=numestados-1;j>=0;j--)
{
temp=matrizc[i][j];
for(k=0;k<contador;k++)
if(estados[k]==temp)
break;
if(k==contador)
{
estados[contador]=temp;
contador++;
}
}
if(contador==numestados)
break;
}
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
for(k=0;k<numestados;k++)
if(matrizc[j][k]==estados[i])
matrizd[j][k]=i;
}
/*Compara dos numeros wolfram y conserva el menor lexicograficamente */
void menor()
{
int temp;
int i,j;
temp=strcmp(clustemp,nw);
if(temp>0)
strcpy(clustemp,nw);
}
/*Obtiene el cluster minimo de una matriz de evolucion */
void cluster()
{
int i,j;
contarestados();
if(estren>=estcol)
{
wolfram(matriz);
strcpy(clustemp,nw);
encontrar(matriz);
for(i=0;i<numedos;i++)
for(j=0;j<numit;j++)
{
asignar((renglon[i]*numit)+j,permutacion);
permutar(permutacion,matriz);
cambioest();
wolfram(matrizd);
menor();
}
strcpy(final,clustemp);
}
if(estcol>=estren)
{
for(i=0;i<numestados;i++)
for(j=0;j<numestados;j++)
matrizb[i][j]=matriz[j][i];
wolfram(matrizb);
strcpy(clustemp,nw);
encontrar(matrizb);
for(i=0;i<numedos;i++)
for(j=0;j<numit;j++)
{
asignar((renglon[i]*numit)+j,permutacion);
permutar(permutacion,matrizb);
cambioest();
wolfram(matrizd);
menor();
}
if(estcol>estren)
strcpy(final,clustemp);
else
if((strcmp(final,clustemp))>0)
strcpy(final,clustemp);
}
}
/*Guarda los clusters encontrados en un archivo */
int lista()
{
int i,j;
int valor=0;
for(i=0;i<totalclusters;i++)
{
for(j=0;j<longcadena;j++)
if(clusters[i][j]!=final[j])
break;
if(j==longcadena)
break;
}
if(i==totalclusters)
{
wolfram(matriz);
for(j=0;j<longcadena;j++)
clusters[i][j]=final[j];
totalclusters++;
hoja=fopen("ACLR4Hl2.TXT","a");
if(totalclusters==1)
fprintf(hoja,"AUTOMATAS CELULARES LINEALES REVERSIBLES 4H con L=2
n
n");
fprintf(hoja,"
nCluster Minimo No.%3d:
",totalclusters);
for(j=0;j<longcadena;j++)
fprintf(hoja,"%c",clusters[totalclusters-1][j]);
fprintf(hoja," Especimen: %s",nw);
fclose(hoja);
valor=1;
}
return valor;
}
/*Calcula las matrices de evolucion estocasticas por estado */
void calculo(int edo)
{
int i;
int cond;
cond=0;
inicializar(edo);
while(cond==0)
{
llenado(edo);
if(checarciclos(edo)==0)
{
conectividad(edo,matrizb);
if((obtenerindices(matrizb,edo,2))==0)
{
if(edo==numestados-1)
{
if(reversible()==0)
{
total++;
cluster();
if(lista()==1)
imprimiravance();
}
}
else
calculo(edo+1);
}
}
borrar(edo);
cond=actualizar(edo);
}
}
/*Cuerpo principal del programa */
void main()
{
int i,j;
totalclusters=total=0;
inicio();
calculo(0);
printf("
nTotal de matrices generadas: %d
n",total);
}