/*****************************************************************************/ /* */ /* forbid.c */ /* */ /* ce programme construit l'arbre de generation des */ /* involutions, permutations, permutations alternantes de [1] a [nmax] */ /* en excluant certains motifs */ /* */ /* syntaxe : */ /* [+] * [-r[+] *] */ /* [-f []] [-noecho] */ /* : suite de caractere indiquant les domaines demandees : */ /* permutation : S(n) */ /* permutation alternante : /\/\/... */ /* involution point fixe : I(n) // points fixes de I(n-1) */ /* involution recurrence : I(n) = I(n-1) + [n-1] * I(n-2) */ /* : suite de caractere indiquant les sorties demandees : */ /* arbre ASCII */ /* permutation et couple de mots de Yamnushi (R-S) */ /* arbre parenthese (environ mot de Dyck) */ /* CABRI */ /* table des nombres de fils, 1 permutation X 1 successeur */ /* regles entre une permutation et tous ses successeurs */ /* table des nombre de fils dans l'arbre de generation */ /* saillants (sig,sid,ssg,ssd) */ /* montees et montees inverses */ /* excedences superieures strictes et larges */ /* indices de 1 et n et valeurs en 1 et n */ /* cycles : nombre et longueur du + long */ /* points fixes */ /* nombre d'inversions */ /* major et major de la permutation inverse */ /* : dimension maximale des permutations a rechercher [<=n_max] */ /* + : relativement a chaque permutation racine */ /* : liste, eventuellement vide, des motifs exclus sur */ /* [3] a [9]...[z], barres ou non */ /* -r : separateur precedant la liste des racines */ /* + : cumul des tables de toutes les racines (listees ou creees) */ /* option par defaut : -r+ */ /* : liste des permutations servant de racines aux */ /* arbres a construire sur [1] a [9]...[z] */ /* -f : separateur precedant le nom du fichier */ /* l'ecran par defaut (si rien n'est precise) */ /* fichier decide par le programme (-f) */ /* fichier choisi par l'utilisateur (-f ) */ /* -noecho : aucun affichage/ecriture_fichier d'explications n'est fait */ /* */ /* ce programme contient un module de gestion d'entiers de taille quelconque */ /* */ /* normalisation : */ /* les constantes sont en majuscules */ /* les types ont leur premiere lettre en majuscule */ /* les variables sont en minuscules */ /* */ /* utilisation avec CABRI : */ /* - executer forbid c ... */ /* - passer sur le MacIntosh */ /* - recuperation du fichier designe par NOMFCABRI avec FTP */ /* . lancer MAC_IP depuis /communication/MAC_IP sur disque dur */ /* . connexion : hostname = 192.33.148.168 (IP du Labri) */ /* . FTP>binary */ /* . FTP>get */ /* . quitter FTP (menu FILE option QUIT) */ /* - affichage du "graphe" */ /* . lancer CABRI */ /* . ouvrir le fichier en format texte */ /* */ /* attention : */ /* - pour la sortie vers CABRI, le programme utilise des commandes du */ /* systeme UNIX : sort, awk, rm */ /* */ /* une permutation sur [n], ie. sur {1,2,...,n} admet n+1 sites (1 a n+1) */ /* rmq.: comme en C les indices commencent a 0, les permutations sont */ /* allouees sur n elements mais le pointeur est immediatement */ /* decremente d'un ; ainsi, on fait varier les indices de 1 a n et les */ /* sites de 1 a n+1 */ /* ex.: vu[] de ctrl1interdit() */ /* tabcoord[] de editcabri() */ /* tabs[] de edparenth() */ /* ->valeurs[] de calc1interdit() */ /* ->valeurs_prec[] de calc1interdit() */ /* ->perm[] de cree1sommet() */ /* */ /* date de creation : 19 Janvier 1992 */ /* */ /* 1ere version : 07/02/92 ; permutations interdites, racines, fic. sortie */ /* 2eme version : 26/03/92 ; perm. interdites barrees, saillants, descentes */ /* 3eme version : 02/05/92 ; filsXfils,regles,montee,excedent,indice, ecran */ /* 4eme version : 10/10/92 ; -noecho */ /* 5eme version : 06/05/92 ; regroupement/accroissement (en nbr) des sorties */ /* 6eme version : 20/12/93 ; sortie couple Yamanushi */ /* 7eme version : 22/12/93 ; domaines , refonte sorties , S/ pts fixes,stats */ /* */ /* auteur : O.G. */ /* */ /*****************************************************************************/ /*===========================================================================*/ /* directives de compilation */ /*===========================================================================*/ /* directive de compilation UNIX ou non */ #define OS_UNIX /*===========================================================================*/ /* #include */ /*===========================================================================*/ #include #ifdef OS_UNIX #include #endif #include /*===========================================================================*/ /* constantes et macros */ /*===========================================================================*/ /*****************************************************************************/ /* definition des constantes */ /*****************************************************************************/ /* constantes booleennes */ #define FAUX (0!=0) #define VRAI (0==0) /* test de parite */ #define ISIMPAIR(nbre) (nbre % 2) /* numero de version du programme */ #define VERSION "7.0 du 22 Decembre 1993" /* informations sur le fichier */ #define INFOS_LABRI "Cet outil a ete developpe pour le LaBRI," #define INFOS_ADR "351 cours de la Liberation, 33405 TALENCE (FRANCE)" #define INFOS_MAIL "Merci d'envoyer vos suggestions a guibert@labri.u-bordeaux.fr" /* separateurs dans la ligne de commande */ #define CARBARRE '-' /* caractere precedant un element barre */ #define SEPRAC "-r" /* liste permutations racines */ #define SEPRACCUM "-r+" /* liste permutations racines pou cumuler tables */ #define SEPFIC "-f" /* fichier */ #define NOECHO "-noecho" /* aucun affichage ecran */ /* valeurs maximales autorisees pour la taille de l'arbre a construire */ #define NBBOOL8 2 /* nombre de Bool8 */ #define NMAX (8 * NBBOOL8 - 1) /* nombres de sites - 1 */ /* indique dans quelle entree on se situe */ #define ININTERDIT 1 #define INRACINE 2 #define INFICHIER 3 /* caractere signifiant que la racine n'a pas ete creee */ #define RACNONCREEE '*' /* indices des domaines possibles */ #define I_DOM_PERM 0 /* permutations */ #define I_DOM_PERMALT 1 /* permutations alternantes */ #define I_DOM_INVOLRECUR 2 /* involutions (par recurrence) */ #define I_DOM_INVOLPTFIX 3 /* involutions (par points fixes) */ #define DIMDOMAINES 4 /* nombre total de domaines */ /* indices des sorties possibles */ #define I_SORTREEL_ARBREASCII 0 #define I_SORTREEL_YAM 1 #define I_SORTREEL_ARBREPARENTH 2 #define I_SORTREEL_CABRI 3 #define I_SORTREEL_2NBFILS 4 #define I_SORTREEL_REGLE 5 #define I_SORTREEL_TTESSTATS 6 #define I_SORTREEL_TABLE 7 #define I_SORTREEL_SIG 8 #define I_SORTREEL_SID 9 #define I_SORTREEL_SSG 10 #define I_SORTREEL_SSD 11 #define I_SORTREEL_M 12 #define I_SORTREEL_MI 13 #define I_SORTREEL_ESL 14 #define I_SORTREEL_ESS 15 #define I_SORTREEL_I_1N 16 #define I_SORTREEL_I_11 17 #define I_SORTREEL_IN 18 #define I_SORTREEL_I1 19 #define I_SORTREEL_CNB 20 #define I_SORTREEL_CLG 21 #define I_SORTREEL_POINTSFIXES 22 #define I_SORTREEL_INVERSIONS 23 #define I_SORTREEL_MAJ 24 #define I_SORTREEL_MAJI 25 /* type de sorties */ #define TYPESORTIEPRCS 1 #define TYPESORTIETABL 2 #define TYPESORTIEGDTABL 3 /* nombre total de sorties reelles par type */ #define DIMSORTREELPRCS 7 #define DIMSORTREELTABL 16 #define DIMSORTREELGDTABL 0 /* 3 */ /* nombre total de sorties reelles */ #define DIMSORTREEL (DIMSORTREELPRCS+DIMSORTREELTABL+DIMSORTREELGDTABL) /* nombre total de sorties visibles par l'utilisateur */ #define DIMSORTUSER 14 /* 16 */ /* quelques indices dans la table des sorties utilisateur */ #define I_SORTUSER_ARBREASCII 0 #define I_SORTUSER_CABRI 3 #define I_SORTUSER_2NBFILS 4 #define I_SORTUSER_TABLE 7 #define I_SORTUSER_MONTEES 9 /* nom des fichiers "ecran" et par defaut */ #define NOMFECRAN "" #define NOMFDEFAUT "forbid.res" /* constantes pour l'edition des racines */ #define NBCARRAC 80 #define LISTERACDEBUT "Liste des racines des " #define LISTERACSUITE "Liste (suite)" /* caracteres indiquant si le site dans la permutation est actif ou inactif */ #define SITEACTIF '_' #define SITEINACTIF '.' /* chaines de caracteres pour editer les permutations en ASCII */ #define STRNLPERM "\n" #define STRTABPERM " " /* dimension 2 tableaux Young associes a perm. */ #define DIM_NMAX_YAM (NMAX+1) /* caractere pour separer les elements de la permutation (Yamanushi) */ #define STRSEPARELEM ' ' /* nombre de caracteres d'edition d'une portion d'un mot de parentheses */ #define NBCARPARENTH 60 #ifdef OS_UNIX /* fichiers pour CABRI */ #define NOMFCABRI "cabri.res" #define NOMFTMPCABRI "cabri.res.tmp" /* format pour CABRI sous MACINTOSH */ #define MAXCARCDE 400 /* nombre maximum de caractere de la commande */ #define CRCABRI '\r' /* retour chariot sous CABRI */ /* coordonnees d'affichage pour CABRI (marges, offsets, tailles) */ /* pour S4() et S1(), S2(), S3() */ #define MRGABS4 10 #define MRGORD4 10 #define OFFABS4 100 #define OFFORD4 30 #define SZSHAP4 3 #define SZFONT4 12 /* pour S5() */ #define MRGABS5 10 #define MRGORD5 10 #define OFFABS5 100 #define OFFORD5 5 #define SZSHAP5 1 #define SZFONT5 3 /* premier numero de sommet CABRI */ #define PREMNUMCABRI 0.0 #endif /* dimension maximale de la table des regles nb_fils X nb_fils ts succ. */ #define MAXREGLEDIFF 500 /* caracteres indicateurs pour la colonne/valeur de la table a editer */ #define INDICCOL 'c' #define INDICVAL 'v' /*****************************************************************************/ /* definition des macros */ /*****************************************************************************/ /* macros rendant le minimum et le maximum de deux elements */ #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) /* macros pour malloc(), calloc(,) et free(), cfree() */ #define MALLOC(t) ((t *) malloc(sizeof(t))) #define CALLOC(n,t) ((t *) calloc((n),sizeof(t))) #define FREE(a) free(a) #ifdef OS_UNIX #define CFREE(a) cfree(a) #else #define CFREE(a) free(a) #endif /* affectation et test des allocations dynamiques */ #define TESTMALLOC(p,t) if (((p)=(t *) malloc(sizeof(t)))==NULL) erreur(0) #define TESTCALLOC(p,n,t) if (((p)=(t *) calloc(n,sizeof(t)))==NULL) erreur(0) /* acces au ieme (i=1..n) element de la permutation sur [n] */ #define PERM(n,i) wperms[(((n)*((n)-1))/2+(i))-1] /* #define PERM(n,i) wperms[indwperms((n),(i))] */ /* macro d'ouverture/fermeture de fichier */ #define FOPEN(f,n) if (f != stdout) \ if ((f = fopen(nomfout == NULL ? (n) : nomfout,"a")) \ == NULL) \ erreur(11) #define FCLOSE(f) if (f != stdout) fclose(f) /*===========================================================================*/ /* types */ /*===========================================================================*/ /*****************************************************************************/ /* "normalisation" des types standards du langage C */ /*****************************************************************************/ typedef void Void; typedef int Int; typedef short Short; typedef long Long; typedef unsigned Unsigned; typedef double Double; typedef float Float; typedef char Char; /*****************************************************************************/ /* definition des types */ /*****************************************************************************/ /*---------------------------------------------------------------------------*/ /* types generaux */ /*---------------------------------------------------------------------------*/ /* pointeurs */ typedef Int * P_Int; typedef Short * P_Short; typedef Long * P_Long; typedef Double * P_Double; typedef Float * P_Float; typedef Char * P_Char; typedef P_Char * PP_Char; typedef FILE * P_FILE; /* type booleen */ typedef Short Booleen; typedef Booleen * P_Booleen; /* definition d'un paquet de 8 booleens binaires (et plus) */ #ifdef OS_UNIX typedef Unsigned Long LongBool; typedef Unsigned Char Bool8; #else typedef Long LongBool; typedef Char Bool8; #endif typedef Bool8 * P_Bool8; typedef P_Bool8 * PP_Bool8; /* type d'un element d'une permutation : 1..nmax */ typedef Char Elem; typedef Elem * P_Elem; typedef P_Elem * PP_Elem; #if (NMAX <= 23) /* (23)*(23-1)/2 = 253 <= 255 = (2**8(==sizeof(Char)))-1 */ typedef Char ElemGd; typedef ElemGd * P_ElemGd; typedef P_ElemGd * PP_ElemGd; #else typedef Int ElemGD; typedef ElemGd * P_ElemGd; typedef P_ElemGd * PP_ElemGd; #endif typedef Char IndDescrip; /*---------------------------------------------------------------------------*/ /* coordonnees CABRI */ /*---------------------------------------------------------------------------*/ #ifdef OS_UNIX typedef Long Indcoordcabri; typedef Indcoordcabri * P_Indcoordcabri; typedef struct Coordcabri * P_Coordcabri; struct Coordcabri { Indcoordcabri abs; /* coordonnee abscisse */ Indcoordcabri ord; /* coordonnee ordonnee */ }; #endif /*---------------------------------------------------------------------------*/ /* resultats du tableau */ /*---------------------------------------------------------------------------*/ /* resultat du tableau */ #ifdef OS_UNIX typedef Double Resultat; #else typedef Long Resultat; #endif typedef Resultat * P_Resultat; /* resultat sous forme d'un entier de taille quelconque */ typedef Long Res; typedef Res * P_Res; typedef P_Res * PP_Res; /* stocke les parametres de l'entier */ typedef struct Valres * P_Valres; struct Valres { Short nb; /* nombre d'entiers stockes */ Short dim; /* nombre de chiffres de max */ Res max; /* == puissance_10(dim) - 1 && <= sizeof(Res) */ }; /* type d'un indice de la table */ typedef Short Indtable; typedef Indtable * P_Indtable; /* structure de la table des regles nb_fils X nb_fils de tous successeurs */ typedef struct Regle * P_Regle; struct Regle { Elem nbfils; /* nombre de fils de la permutation pere */ P_Elem lstnbfils; /* liste des nombres de fils permutations filles */ P_Booleen lstvu; /* indicateurs de "visite" des elements */ }; /*---------------------------------------------------------------------------*/ /* stocke les parametres d'edition en CABRI */ /*---------------------------------------------------------------------------*/ #ifdef OS_UNIX typedef struct ParamCabri * P_ParamCabri; struct ParamCabri { Int mrgabs; /* marge en abscisse */ Int mrgord; /* marge en ordonnee */ Int offabs; /* offset en abscisse */ Int offord; /* offset en ordonnee */ Short szshap; /* size of shape */ Short szfont; /* taille de la fonte */ }; #endif /*---------------------------------------------------------------------------*/ /* permutations interdites */ /*---------------------------------------------------------------------------*/ /* differences entre un element d'une permutation et ses predecesseurs */ struct Diff { Booleen inconnu; /* cette difference est-elle connue ou non ? */ Short val; /* valeur de la difference retenue: + faible val. absolue */ Elem ind; /* indice de l'element predecesseur ayant ete retenu */ }; /* informations calculees pour les permutations interdites */ typedef struct ValInterdit * P_ValInterdit; struct ValInterdit { Elem elem; /* un element de la permutation (interdite) */ Elem elemtst; /* element de la permutation correspondante a tester */ struct Diff diffneg; /* differences negatives */ struct Diff diffpos; /* differences positives */ }; /* informations d'une permutation interdite sur [n+1] */ typedef struct Interdit * P_Interdit; struct Interdit { Elem n_suiv; /* nombre d'elements de la permutation sur [n+1] */ P_ValInterdit valeurs_suiv; /* perm. sur [n+1], differences calc. */ Elem n; /* nombre d'elements de la permutation sur [n] */ Elem site; /* site d'insertion de n+1 dans [n] tq Pn+1(site)==n+1 */ P_ValInterdit valeurs; /* permutation sur [n], differences calculees */ Elem n_prec; /* nombre d'elements de la permutation sur [n-1] */ Elem site_prec; /* site d'insertion n dans [n-1] tq Pn(site_prec)==n */ Elem site_suiv; /* site d'insertion theorique de n+1 dans [n-1] */ P_ValInterdit valeurs_prec; /* permuta. sur [n-1], differences calc. */ P_Interdit suiv; /* pointe sur la permutation interdite suivante */ }; /* Exemple : permutation interdite = 2647531 = P7() sur [7] n_suiv = 7 (7) (1) (2) (3) (4) (5) (6) (7) valeurs_suiv->elem 2 6 4 7 5 3 1 ->diffneg.inconnu V V F V F F F .val -2 -1 -1 -1 .ind 2 2 3 1 ->diffpos.inconnu V F F F F F V .val +4 +2 +1 +1 +1 .ind 1 1 2 3 1 n = 6 (7-1) site = 4 (P7(site)==7) (1) (2) (3) (4) (5) (6) valeurs->elem 2 6 4 5 3 1 ->diffneg.inconnu V V F F F F .val -2 -1 -1 -1 .ind 2 2 3 1 ->diffpos.inconnu V F F F F V .val +4 +2 +1 +1 .ind 1 1 3 1 n_prec = 5 (7-2) site_prec = 2 (P6(site_prec)==6) site_suiv = 3 (==site-1 car site>site_prec) (1) (2) (3) (4) (5) valeurs_prec->elem 2 4 5 3 1 ->diffneg.inconnu V V V F F .val -1 -1 .ind 2 1 ->diffpos.inconnu V F F F V .val +2 +1 +1 .ind 1 2 1 */ /* informations d'une permutation interdite barree sur [n] */ typedef struct Barre * P_Barre; struct Barre { Elem n; /* nombre d'elements de la permutation sur [n] */ Bool8 isbarre[NBBOOL8]; /* indique si un element est barre ou non */ P_ValInterdit valeurs; /* permutation sur [n], differences calculees */ Elem nnonbarre; /* nombre elements non barres de permutation sur [n] */ P_ValInterdit valnonbarre; /* permuta. sans barre, differences calc. */ Elem ielemtst[NMAX+2]; /* stocke les indices des elements testes */ Elem inonbarre[NMAX+2]; /* stocke indices des elements non barres */ P_Barre suiv; /* pointe sur la permutation interdite barree suivante */ }; /* Exemple : permutation interdite barree = 3-7-461-25 = P7() sur [7] avec 3 elements barres (742) et 4 autres (3615) de la forme 2413 n = 7 (1) (2) (3) (4) (5) (6) (7) isbarre F V V F F V F (1) (2) (3) (4) (5) (6) (7) valeurs->elem 3 7 4 6 1 2 5 ->diffneg.inconnu V V F F F F F .val -1 -1 -2 -1 -1 .ind 7 2 1 1 4 ->diffpos.inconnu V F F F V F F .val +1 +1 +2 +1 +1 .ind 4 1 3 5 3 attention a diffneg[3] et a diffpos[2] nnonbarre = 4 (1) (2) (3) (4) valnonbarre->elem 2 4 1 3 ->diffneg.inconnu V V F F .val -1 -1 .ind 1 2 ->diffpos.inconnu V F V F .val +2 +1 .ind 1 1 (0) (1) (2) (3) (4) (5) ... inonbarre 0==0 1 4 5 7 8==n+1 ... */ /*---------------------------------------------------------------------------*/ /* arbre des involutions/permutations retenues */ /*---------------------------------------------------------------------------*/ /* sommet de l'arbre qui correspond a une permutation sur [n] */ typedef struct Sommet * P_Sommet; struct Sommet { Elem n; /* nombre d'elements de la permutation sur [n] */ P_Elem perm; /* elements de la permutation sur [n] */ Elem nbfils; /* nombre de fils de [n] sur [n+1] */ Elem nbsig; /* nombre de saillants inferieurs a gauche de [n] */ Elem nbsid; /* nombre de saillants inferieurs a droite de [n] */ Elem nbssg; /* nombre de saillants superieurs a gauche de [n] */ Elem nbssd; /* nombre de saillants superieurs a droite de [n] */ Elem nbm; /* nombre de montees de [n] */ Elem nbmi; /* nombre de montees inverses de [n] */ Elem nbesl; /* nombre d'excedences superieurs larges de [n] */ Elem nbess; /* nombre d'excedences superieurs strictes de [n] */ Elem nbii_1n; /* indice de n dans [n] */ Elem nbii_11; /* indice de 1 dans [n] */ Elem nbiin; /* perm(n) dans [n] */ Elem nbii1; /* perm(1) dans [n] */ Elem nbcnb; /* nombre de cycles dans [n] */ Elem nbclg; /* longueur du + long cycle dans [n] */ Elem nbpf; /* nombre de points fixes de [n] */ ElemGd nbinv; /* nombre d'inversions de [n] */ ElemGd nbmaj; /* indice du major de [n] */ ElemGd nbmaji; /* indice du major inverse de [n] */ Bool8 sitesactifs[NBBOOL8]; /* sites d'insertion des [n+1] */ Elem site; /* site d'insertion de n dans [n-1] */ P_Sommet filsaine; /* pointe sur le premier fils [n+1] */ P_Sommet suiv; /* pointe sur la permutation "frere" sur [n] suivante */ }; /* Exemple : permutation 42351 de T(132) n = 5 site = 4 (P(4)==5) (1) (2) (3) (4) (5) perm 4 2 3 5 1 (1) (2) (3) (4) (5) (6) sitesactifs V F F F V V nbfils = 3 nbsig = 3 (P(1)==4, P(2)==2, P(5)==1) nbsid = 1 (P(5)==1) nbssg = 2 (P(1)==4, P(4)==5) nbssd = 2 (P(5)==1, P(4)==5) nbm = 2 (P(2)==2=1, P(2)==2>=2, P(3)==3>=3, P(4)==5>=4) nbess = 2 (P(1)==4>1, P(4)==5>4) nbii_1n = 4 (P(4)==5) nbii_11 = 5 (P(5)==1) nbiin = 1 (P(5)==1) nbii1 = 4 (P(1)==4) nbcnb = 3 (42351==(1,4,5)(2)(3)) nbclg = 3 (3==|(1,4,5)|) nbpf = 2 (P(2)==2,P(3)==3) nbinv = 6 (P(1)==4g,>d)", 'm',FAUX,TYPESORTIETABL,"montees.res", "Tables des montees (montees,montees inverses)", 'e',FAUX,TYPESORTIETABL,"excedences.res", "Tables des excedences (pi(i) >=,> i)", 'i',FAUX,TYPESORTIETABL,"indices.res", "Tables des indices (pi-1(n),pi-1(1),pi(n),pi(1))", 'y',FAUX,TYPESORTIETABL,"cycles.res", "Tables des cycles (nombre,longueur max.)", 'x',FAUX,TYPESORTIETABL,"pts_fixes.res","Table des points fixes"}; /*, 'I',FAUX,TYPESORTIEGDTABL,"inversions.res","Table des inversions", 'M',FAUX,TYPESORTIEGDTABL,"major.res", "Table des majors (major,major inverse)"}; */ struct SortieReelle { IndDescrip refuser; /* reference au pere ds la table sorties user */ Short min; /* indice minimum pour TYPESORTIETABL */ Short max; /* indice maximum // n pour TYPESORTIETABL */ P_Char txt; /* texte */ P_Char lib; /* libelle d'entete de table */ } sortreel[DIMSORTREEL] = { 0,9,-9,"Arbre ASCII","", 1,9,-9,"Permutation et couple de mots de Yamanushi","", 2,9,-9,"Arbre de parentheses","", 3,9,-9,"CABRI","", 4,9,-9,"Table des nombres de fils, 1 permutation X 1 successeur","", 5,9,-9,"Regles entre une permutation X tous successeurs","", 6,9,-9,"Toutes les statistiques","", 7,0,1,"Table des nombres de fils","#fils", 8,1,0,"Table des saillants inferieurs a gauche", "#saillants inferieurs gauches", 8,1,0,"Table des saillants inferieurs a droite", "#saillants inferieurs droits", 8,1,0,"Table des saillants superieurs a gauche", "#saillants superieurs gauches", 8,1,0,"Table des saillants superieurs a droite", "#saillants superieurs droits", 9,0,-1,"Table des montees","#montees", 9,0,-1,"Table des montees inverses","#montees inverses", 10,1,0,"Table des excedences superieurs larges", "#excedences superieurs larges", 10,0,-1,"Table des excedences superieurs strictes", "#excedences superieurs strictes", 11,1,0,"Table des indices du plus grand element","indice de n", 11,1,0,"Table des indices du plus petit element","indice de 1", 11,1,0,"Table des elements en derniere position","dernier element", 11,1,0,"Table des elements en premiere position","premier element", 12,1,0,"Table des nombres de cycles","#cycles", 12,1,0,"Table des longueurs des plus longs cycles","lg + long cycle", 13,0,0,"Table des points fixes","#points fixes"}; /*, 14,9,-9,"Table des inversions","#inversions", 15,9,-9,"Table des majors","major", 15,9,-9,"Table des majors inverses","major inverse"}; */ /*===========================================================================*/ /* declaration des fonctions */ /*===========================================================================*/ /* Void main(); */ /* Int P_Char[] */ Void ctrl(); /* Int P_Char[] */ Void ctrl1arg(); /* P_Char Short P_Char P_Booleen P_Booleen */ Void ctrldomaines(); /* P_Char */ Void ctrlsorties(); /* P_Char */ Int calcnmax(); /* P_Char */ Short ctoi(); /* Char */ Booleen ischiffelem(); /* Char */ Elem ctoelem(); /* Char */ Char elemtoc(); /* Elem */ Elem ctrl1perm(); /* P_Char P_Elem P_Elem Booleen */ Void cree1interdit(); /* P_Char Elem Elem */ Void cree1barre(); /* P_Char Elem Elem */ Void creenonbarre(); /* P_Char P_Char Elem Elem P_Bool8 */ P_ValInterdit calc1interdit(); /* P_Char Elem */ Void calc1diff(); /* P_ValInterdit P_ValInterdit Elem */ P_Sommet cree1sommet(); /* Elem Elem P_Racine */ P_Elem cree1perm(); /* Elem */ Booleen isinvol(); /* Elem */ Void creeracinesdefaut(); /* Short */ Booleen creeracinesuser(); /* Short Elem Elem */ P_Racine cree1racine(); /* PP_Racine Short Elem Elem */ Void initquetable(); /* */ Void edligcde(); /* Int P_Char[] */ Void affligcde(); /* P_FILE Int P_Char[] */ Void cons(); /* */ Void consperm(); /* */ Void gotperm(); /* Booleen Elem P_Bool8 Elem P_Racine P_Valres P_Res */ Void goperm(); /* Booleen Elem P_Bool8 P_Sommet Elem P_Bool8 P_Racine */ Void conspermalt(); /* */ Void gopermalt(); /* Booleen Elem P_Sommet P_Racine */ Void consinvolrecur(); /* */ Void goinvolrecur(); /* Booleen Elem P_Sommet P_Racine */ Void consinvolptfix(); /* */ Void goinvolptfix(); /* Booleen Elem P_Sommet P_Racine */ P_Sommet ajoutfils(); /* P_Sommet Elem Elem P_Racine */ Void creeracdom(); /* IndDescrip Short Elem Elem */ Booleen tstracine(); /* Elem */ Booleen tstvalide(); /* Elem Elem P_Bool8 Elem */ Booleen tst1interdit(); /* Elem Elem Elem P_Interdit Booleen */ Booleen tstbarrvalide(); /* Elem Elem */ Booleen tst1barre(); /* Elem P_Barre */ Booleen tstdiffbarre(); /* Elem Elem Elem P_ValInterdit Elem P_Barre */ Booleen tstdiffttbarre(); /* Elem Elem Elem Elem Elem P_ValInterdit Elem P_Barre */ Booleen tstdiff1(); /* Elem Elem Elem P_ValInterdit Elem */ Booleen tstdiff2(); /* Elem Elem Elem Elem Elem P_ValInterdit Elem */ Booleen tstdiff3(); /* Elem Elem Elem Elem Elem Elem Elem P_ValInterdit Elem */ Booleen tst1diff(); /* Elem Elem Elem P_ValInterdit P_ValInterdit */ Int calcdimwperms(); /* Int */ Void initwperms(); /* P_Racine */ Void iniperm(); /* Elem */ Void inipermalt(); /* Elem */ Void cppermsite(); /* Elem Elem */ Elem cpperm(); /* Elem */ Void mvperm(); /* Elem P_Elem */ Booleen tstperm(); /* Elem */ Void echpfperm(); /* Elem Elem */ P_Elem adrperm(); /* Elem */ Indtable indwperms(); /* Elem Elem */ Elem calcpf(); /* P_Elem Elem */ Elem calcssd(); /* P_Elem Elem */ Elem calcssg(); /* P_Elem Elem */ Elem calcsid(); /* P_Elem Elem */ Elem calcsig(); /* P_Elem Elem */ Elem calcm(); /* P_Elem Elem */ Elem calcd(); /* P_Elem Elem */ Elem calcmi(); /* P_Elem Elem */ Elem calcmi2(); /* P_Elem Elem */ Elem calcdi(); /* P_Elem Elem */ Elem calcess(); /* P_Elem Elem */ Elem calceis(); /* P_Elem Elem */ Elem calcesl(); /* P_Elem Elem */ Elem calceil(); /* P_Elem Elem */ Elem calcii_1n(); /* P_Elem Elem */ Elem calcii_11(); /* P_Elem Elem */ Elem calciin(); /* P_Elem Elem */ Elem calcii1(); /* P_Elem Elem */ Elem calccnb(); /* P_Elem Elem */ Elem calcclg(); /* P_Elem Elem */ ElemGd calcinv(); /* P_Elem Elem */ ElemGd calcmaj(); /* P_Elem Elem */ ElemGd calcmaji(); /* P_Elem Elem */ P_Elem inverseperm(); /* P_Elem Elem */ Void edit(); /* */ Void edit1dom(); /* IndDescrip */ Void prcsforet(); /* IndDescrip Void(*)() */ Void editascii(); /* P_Racine P_Sommet */ Void edascii(); /* P_Racine P_Sommet P_Booleen */ Void affascii(); /* P_Racine P_Sommet P_Booleen */ Void edityam(); /* P_Racine P_Sommet */ Void edyam(); /* P_Racine P_Sommet */ Void affyam(); /* P_Sommet */ Void aff1yam(); /* P_Elem P_Elem Elem */ Void editparenth(); /* P_Racine P_Sommet */ P_Char edparenth(); /* P_Sommet */ Booleen cmpparenth(); /* P_Char P_Char */ Void affmotparenth(); /* P_Char */ Void editcabri(); /* P_Racine P_Sommet */ Void afftetecabri(); /* Resultat */ Resultat numcabri(); /* P_Racine P_FILE P_Sommet Resultat P_Resultat P_Coordcabri P_ParamCabri P_Indcoordcabri */ Void affpermcabri(); /* P_FILE P_Sommet Resultat Resultat P_Resultat P_Coordcabri P_ParamCabri Indcoordcabri */ Void fusioncabri(); /* */ Void edit2nbfils(); /* P_Racine P_Sommet */ Indtable calcdim2nbfils(); /* Elem */ Void ed2nbfils(); /* P_Sommet P_Sommet Elem P_Res */ Indtable indtab2nbfils(); /* Elem Elem Elem */ Void aff2nbfils(); /* Elem P_Res Indtable P_Valres */ Void editregle(); /* P_Racine P_Sommet */ Void edregle(); /* P_Sommet P_Regle P_Indtable P_Booleen */ Booleen existregle(); /* P_Sommet P_Regle Indtable */ Booleen creeregle(); /* P_Sommet P_Regle P_Indtable */ Void liberegle(); /* P_Regle Indtable */ Void affregle(); /* P_Regle Indtable Booleen */ Void editstats(); /* P_Racine P_Sommet */ Void edstats(); /* P_Sommet */ Void prcstable(); /* IndDescrip IndDescrip */ Void edittable(); /* IndDescrip IndDescrip P_Racine P_Sommet P_Res P_Valres Elem */ Void inittable(); /* Resultat Elem P_Valres PP_Res P_Indtable */ Void edtable(); /* IndDescrip P_Racine P_Sommet Elem P_Res P_Valres */ Indtable indtable(); /* Elem P_Valres Char Elem Elem */ Void afftable(); /* IndDescrip IndDescrip Elem Elem P_Res P_Valres */ Void afftabltete(); /* Elem Elem P_Res P_Valres */ Void afftablpied(); /* Elem Elem P_Short */ Void afftablcorps(); /* Short Short Elem Elem P_Res P_Valres P_Short */ Void cumultables(); /* P_Res P_Valres Elem P_Res P_Valres Elem Elem */ Void creetablcum(); /* P_Racine Booleen P_Valres PP_Res P_Indtable P_Resultat P_Elem */ Resultat calcmaxnbperm(); /* Elem Elem */ Void calcvalres(); /* Resultat P_Valres */ Void razresultat(); /* P_Valres P_Res */ Void incresultat(); /* P_Valres P_Res */ Void addresultat(); /* P_Valres P_Res P_Res */ Void cpresultat(); /* P_Valres P_Res P_Res */ Short nbcresultat(); /* P_Valres P_Res */ Void affresultat(); /* P_Valres P_Res Short */ Void inibool8(); /* P_Bool8 Booleen */ Void mvbool8(); /* P_Bool8 Elem Booleen */ Booleen tstbool8(); /* P_Bool8 Elem */ Void ptebool8(); /* PP_Bool8 P_Elem */ Void cpbool8(); /* P_Bool8 P_Bool8 */ Elem cptenbfils(); /* P_Bool8 */ Void editrac(); /* */ Void editrac1dom(); /* P_FILE IndDescrip */ Void libe(); /* */ Void libetsinterdits(); /* */ Void libe1interdit(); /* P_Interdit */ Void libe1barre(); /* P_Barre */ Void libetsracines(); /* PP_Racine */ Void libe1racine(); /* PP_Racine */ Void libearbre(); /* P_Sommet */ Void libe1sommet(); /* P_Sommet */ Void libe1perm(); /* P_Elem */ Void warning(); /* Short */ Void erreur(); /* Short */ Void affsyntaxecde(); /* */ /*===========================================================================*/ /* programme principal */ /*===========================================================================*/ /*****************************************************************************/ /* construit l'arbre generation des involutions/permutations a motifs exclus */ /*****************************************************************************/ Void main(argc,argv) Int argc; /* nombre d'arguments de la ligne de commande */ P_Char argv[]; /* chaines de caracteres contenant les arguments */ { Int iargv0; /* initialisation de echo */ echo = strcmp(argv[argc-1],NOECHO); /* reconstitution du nom du programme executable nompg */ nompg = argv[0]; for (iargv0 = 0; argv[0][iargv0]; iargv0++) if (argv[0][iargv0] == '/') nompg = argv[0] + iargv0 + 1; /* debut du programme */ if (echo) printf("\nDebut du programme %s version %s\n",nompg,VERSION); if (echo) printf("Debut des controles et initialisations\n"); /* traitement principal */ ctrl((echo ? argc : (argc - 1)),argv); if (echo) edligcde(argc,argv); if (echo) printf("Debut de la construction des arbres\n"); cons(); if (! quetable) { if (echo) printf("Debut des editions\n"); edit(); if (echo) printf("Debut des liberations memoires\n"); } editrac(); libe(); /* fin du programme */ if (echo) printf("Fin du programme %s\n\n",nompg); } /*===========================================================================*/ /* controle des arguments de la ligne de commande */ /*===========================================================================*/ /*****************************************************************************/ /* controle des arguments passes en parametre a la ligne de commande */ /*****************************************************************************/ Void ctrl(argc,argv) Int argc; /* nombre d'arguments de la ligne de commande */ P_Char argv[]; /* chaines de caracteres contenant les arguments */ { Int iargv; /* indice de argv[] */ Int nmax; /* variable temporaire pour calculer nmax des racines */ Int dimwperms; /* dimension de wperms[] */ Booleen indicracine; /* indique si une racine a ete renseignee ou non */ Char dans; /* indique dans quel type d'entree on se situe (motif,rac.,fic.) */ Booleen fichierdde; /* indique si le type de sortie "-f" a ete demande */ /* la commande doit avoir au - 4 argts : elle-meme, domaine, type S/, nmax */ if (argc < 4) erreur(1); /* controle des domaines : permutation,permutation alt.,involutions (2) */ ctrldomaines(argv[1]); /* controle des types de sorties demandees */ ctrlsorties(argv[2]); initquetable(); /* controle du nombre maximum des permutations sur [nmax] a tester */ nmax = calcnmax(argv[3]); /* < 0 si '+' absent, >= 0 si '+' present */ if ((nmax < 0 && - nmax > NMAX) || (nmax >= 0 && nmax > NMAX)) erreur(4); /* initialisation de wperms[] */ dimwperms = calcdimwperms(nmax); TESTCALLOC(wperms,dimwperms,Elem); /* controle des motifs exclus, permutations racines, du fichier */ nomfout = NULL; fout = NULL; /* pour que ce soit different de stdout */ tablesacumuler = VRAI; indicracine = FAUX; dans = ININTERDIT; fichierdde = FAUX; for (iargv = 4; iargv < argc; iargv++) ctrl1arg(argv[iargv],nmax,&dans,&indicracine,&fichierdde); if (! indicracine) creeracinesdefaut(nmax); if (! fichierdde) { fout = stdout; nomfout = NOMFECRAN; } } /*****************************************************************************/ /* controle d'un argument */ /*****************************************************************************/ Void ctrl1arg(s,nmax,p_dans,p_indicracine,p_fichierdde) P_Char s; /* pointe sur l'argument */ Short nmax; /* variable temporaire pour calculer nmax des racines */ P_Char p_dans; /* pointe sur indicateur du type d'entree on se situe */ P_Booleen p_indicracine; /* pointe sur indicateur pour une racine renseignee */ P_Booleen p_fichierdde; /* pointe sur indicateur pour un fichier demande */ { if (! (strcmp(SEPRAC,s) && strcmp(SEPRACCUM,s))) if (*p_dans < INRACINE) { tablesacumuler = strcmp(SEPRAC,s); *p_dans = INRACINE; } else erreur(20); else if (! strcmp(SEPFIC,s)) if (*p_dans < INFICHIER) { *p_fichierdde = VRAI; *p_dans = INFICHIER; } else erreur(20); else switch (*p_dans) { Elem nbarre; /* nombre d'elements barres */ Elem n; /* nombre d'elements de la permutation sur [n] */ Elem site; /* site d'insertion de n sur la permutation [n-1] */ Elem i; /* indice de la permutation */ Booleen creee; /* indique si rac. user est reellement creee */ case ININTERDIT : if ((nbarre = ctrl1perm(s,&n,&site,VRAI)) == 0) cree1interdit(s,n,site); else cree1barre(s,n,nbarre); break; case INRACINE : if (ctrl1perm(s,&n,&site,FAUX) != 0) erreur(16); for (i = 1; i <= n; i++) PERM(n,i) = ctoelem(s[i - 1]); iniperm(n); creee = tstracine(n); if (creee) creee = creeracinesuser(nmax,n,site); if (creee) *p_indicracine = VRAI; else for (i = 0; i < n; i++) s[i] = RACNONCREEE; break; case INFICHIER : if (nomfout == NULL) nomfout = s; else erreur(13); break; default : erreur(14); break; } } /*****************************************************************************/ /* controle des domaines des involutions/permutations */ /*****************************************************************************/ Void ctrldomaines(s) P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ { Booleen aumoins1domaine; /* indique si au moins 1 domaine est demande */ aumoins1domaine = FAUX; for ( ; *s; s++) { IndDescrip idomaine; /* indice des domaines */ Booleen trouve; /* indique si le caractere teste est bien un domaine */ trouve = FAUX; idomaine = 0; while (idomaine < DIMDOMAINES && ! trouve) if (domaines[idomaine].carrepr == *s) trouve = VRAI; else idomaine++; if (trouve && ! domaines[idomaine].dde) { domaines[idomaine].dde = VRAI; aumoins1domaine = VRAI; } } if (! aumoins1domaine) erreur(21); } /*****************************************************************************/ /* controle des sorties */ /*****************************************************************************/ Void ctrlsorties(s) P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ { Booleen aumoins1sortie; /* indique si au moins 1 sortie est demandee */ aumoins1sortie = FAUX; for ( ; *s; s++) { IndDescrip isortuser; /* indice de sorties utilisateur */ Booleen trouve; /* indique si le caractere teste est bien un sortie */ trouve = FAUX; isortuser = 0; while (isortuser < DIMSORTUSER && ! trouve) if (sortuser[isortuser].carrepr == *s) trouve = VRAI; else isortuser++; if (trouve && ! sortuser[isortuser].dde) { sortuser[isortuser].dde = VRAI; aumoins1sortie = VRAI; } } if (! aumoins1sortie) erreur(2); } /*****************************************************************************/ /* transforme une chaine de caracteres en l'entier qui lui correspond */ /*****************************************************************************/ Int calcnmax(s) P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ { Int i; /* valeur numerique du nombre */ Short signe; /* signe de l'entier : < 0 si '+' absent, >= 0 si '+' present */ if (*s == '+') { signe = 1; s++; } else signe = -1; for (i = 0; *s; s++) if (*s < '0' || *s > '9') erreur(3); else i = 10 * i + ctoi(*s); return(signe * i); } /*****************************************************************************/ /* transforme un caractere chiffre en l'entier qui lui correspond */ /*****************************************************************************/ Short ctoi(c) Char c; /* caractere contenant le chiffre */ { return(c - '0'); } /*****************************************************************************/ /* teste si le caractere est bien Elem (1..9,a..z) */ /*****************************************************************************/ Booleen ischiffelem(c) Char c; /* caractere contenant le chiffre */ { return((c >= '1' && c <= '9') || (c >= 'a' && c <= 'z')); } /*****************************************************************************/ /* transforme un caractere en l'entier Elem (1..9,a..z) qui lui correspond */ /*****************************************************************************/ Elem ctoelem(c) Char c; /* caractere contenant l'element */ { return(c <= '9' ? (c - '0') : (c - 'a' + 10)); } /*****************************************************************************/ /* transforme un entier Elem (1..9,a..z) en le caractere qui lui correspond */ /*****************************************************************************/ Char elemtoc(e) Elem e; /* element a convertir en caractere */ { return(e <= 9 ? (e + '0') : (e + 'a' - 10)); } /*****************************************************************************/ /* controle d'une permutation */ /*****************************************************************************/ Elem ctrl1perm(s,p_n,p_site,perminterdite) /* retourne le nombre d'elements barres rencontres */ P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ P_Elem p_n; /* pointe sur la dimension de la permutation */ P_Elem p_site; /* pointe sur le site d'insertion de la permutation */ Booleen perminterdite; /* controle d'une permutation interdite */ { P_Char sv_s; /* sauvegarde du parametre s */ Short nbarre; /* nombre d'elements barres */ Short n; /* dimension de la permutation */ Short nmaxi; /* valeur de l'element le + grand de la permutation */ Short imaxi; /* indice de nmaxi */ P_Booleen vu; /* pointe sur un tableau d'indicateurs d'element visite ou non */ Short ivu; /* indice dans le tableau vu[] */ /* calcul de la dimension de la permutation */ sv_s = s; nbarre = 0; n = 0; nmaxi = 0; do { if (*s == CARBARRE) if (perminterdite) if (ischiffelem(*(s+1))) nbarre++; else erreur(17); else erreur(16); else { if (! ischiffelem(*s)) erreur(5); n++; if (ctoelem(*s) > nmaxi) { nmaxi = ctoelem(*s); imaxi = n; } } s++; } while (*s); if (n != nmaxi) erreur(6); /* verifie s'il s'agit bien d'une permutation [1]||[3]..[9],[a]..[z] */ TESTCALLOC(vu,n,Booleen); vu--; for (ivu = 1; ivu <= n; ivu++) vu[ivu] = FAUX; for (s = sv_s; *s; s++) if (*s != CARBARRE) if (vu[ctoelem(*s)]) erreur(6); else vu[ctoelem(*s)] = VRAI; CFREE(vu+1); /* controle pour la permutation interdite */ if (perminterdite) if ((nbarre == 0 && n <= 2) || (nbarre != 0 && n == nbarre)) erreur(7); if (n > NMAX) erreur(15); /* affectations finales */ *p_n = (Elem) n; *p_site = (Elem) imaxi; return((Elem) nbarre); } /*****************************************************************************/ /* creation de la structure necessaire au stockage d'1 permutation interdite */ /*****************************************************************************/ Void cree1interdit(s,n,site) /* NB.: on stocke [n-1] en conservant le site d'insertion de n */ P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ Elem n; /* nombre d'elements de la permutation sur [n] */ Elem site; /* site d'insertion de n sur la permutation [n-1] */ { Elem i; /* indice de la permutation sur [n-1] */ Char strperm[NMAX+1]; /* chaine caracteres contenant permutation sur [n-1] */ P_Interdit pi; /* pointe sur la nouvelle permutation interdite */ P_Interdit piprec; /* pointeur precedent dans liste permutations interdites */ P_Interdit picrte; /* pointeur courant dans liste permutations interdites */ Booleen fini; /* creation de la structure */ TESTMALLOC(pi,struct Interdit); /* enregistre les valeurs de la permutation interdite */ /* sur [n+1] */ pi->n_suiv = n; pi->valeurs_suiv = calc1interdit(s,n+1); /* sur [n] */ pi->n = n - 1; pi->site = site; pi->valeurs = calc1interdit(s,n); /* sur [n-1] */ pi->n_prec = n - 2; i = 0; for ( ; *s; s++) if (ctoelem(*s) != n) { strperm[i] = *s; i++; if (ctoelem(*s) + 1 == n) pi->site_prec = i; } strperm[i] = '\0'; pi->valeurs_prec = calc1interdit(strperm,n-1); pi->site_suiv = site > pi->site_prec ? (site - 1) : site; /* insertion ds la liste chainee par ordre croissant de dimension */ picrte = lstinterdit; piprec = NULL; fini = FAUX; while (picrte != NULL && ! fini) if (picrte->n < pi->n) { piprec = picrte; picrte = picrte->suiv; } else fini = VRAI; if (piprec == NULL) lstinterdit = pi; else piprec->suiv = pi; pi->suiv = picrte; } /*****************************************************************************/ /* creation structure necessaire pr stocker 1 permutation interdite barree */ /*****************************************************************************/ Void cree1barre(s,n,nbarre) /* NB.: on stocke [n-1] en conservant le site d'insertion de n */ P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ Elem n; /* nombre d'elements de la permutation sur [n] */ Elem nbarre; /* nombre d'elements barres */ { Char strperm[NMAX+1]; /* chaine caracteres contenant permutation sur [n-1] */ Elem i; /* indice de la permutation sur [n] */ Elem iinonb; /* indice de inonbarre[] */ P_Barre pib; /* pointe sur la nouvelle permutation interdite barree */ P_Barre pibprec; /* pointr precedent dans liste permuta. interdites barrees */ P_Barre pibcrte; /* pointr courant ds liste permutations interdites barrees */ Booleen fini; /* creation de la structure */ TESTMALLOC(pib,struct Barre); /* enregistre les valeurs de la permutation interdite */ /* sur [n] */ pib->n = n; pib->valeurs = calc1interdit(s,n+1); /* de la permutation des elements non barres */ pib->nnonbarre = n - nbarre; creenonbarre(strperm,s,n,pib->nnonbarre,pib->isbarre); pib->valnonbarre = calc1interdit(strperm,pib->nnonbarre+1); /* modification des valeurs sur [n] et de pib->inonbarre[] */ pib->ielemtst[0] = 0; pib->inonbarre[0] = 0; pib->inonbarre[pib->nnonbarre + 1] = pib->n + 1; iinonb = 0; for (i = 1; i <= pib->n; i++) if (tstbool8(pib->isbarre,i)) { Elem j; /* indice des successeurs de i */ for (j = i + 1; j <= pib->n; j++) if (! tstbool8(pib->isbarre,j)) calc1diff(pib->valeurs+i,pib->valeurs+j,j); } else { iinonb++; pib->inonbarre[iinonb] = i; } /* insertion ds la liste chainee par ordre croissant de dimension */ pibcrte = lstbarre; pibprec = NULL; fini = FAUX; while (pibcrte != NULL && ! fini) if (pibcrte->nnonbarre < pib->nnonbarre || (pibcrte->nnonbarre == pib->nnonbarre && pibcrte->n < pib->n)) { pibprec = pibcrte; pibcrte = pibcrte->suiv; } else fini = VRAI; if (pibprec == NULL) lstbarre = pib; else pibprec->suiv = pib; pib->suiv = pibcrte; } /*****************************************************************************/ /* affectation des elements non barres de la permutation interdite barree */ /*****************************************************************************/ Void creenonbarre(d,s,n,nnonbarre,p_isbarre) P_Char d; /* pointe sur la chaine de caracteres destinataire */ P_Char s; /* pointe sur la chaine de caracteres source */ Elem n; /* nombre total d'elements de la permutation barree */ Elem nnonbarre; /* nombre d'elements non barres de la permutation barree */ P_Bool8 p_isbarre; /* pointe sur indicateurs chaque element : barre ou non */ { Elem i; /* indice de la permutation destinataire */ Elem site; /* site d'un element de la permutation source */ Elem e; /* element a placer */ /* initialisation (extrait la sous-sequence) de d[] et calcul de p_isbarre */ inibool8(p_isbarre,FAUX); site = 1; i = 0; for ( ; *s; s++) { if (*s == CARBARRE) { s++; mvbool8(p_isbarre,site,VRAI); } else { d[i] = *s; i++; } site++; } d[i] = '\0'; /* retraitement de d[] pour obtenir une permutation sur [nnonbarre] */ for (e = 1; e <= nnonbarre; e++) { Elem mini; /* plus petit element >= e */ /* recherche du plus petit element >= e */ mini = n; for (i = 0; i < nnonbarre; i++) { Elem etst; /* element teste */ etst = ctoelem(d[i]); if (etst >= e && etst < mini) mini = etst; } /* diminution des valeurs trop grandes */ if (mini > e) for (i = 0; i < nnonbarre; i++) { Elem etst; /* element teste */ etst = ctoelem(d[i]); if (etst >= mini) d[i] = elemtoc(etst + e - mini); } } } /*****************************************************************************/ /* affectation des elements de la permutation interdite et calculs associes */ /*****************************************************************************/ P_ValInterdit calc1interdit(s,n) P_Char s; /* pointe sur le 1er caractere de la chaine a traiter */ Elem n; /* nombre d'elements de la permutation sur [n] */ { Elem i; /* indice */ P_ValInterdit pvi; /* pointe sur nvelle struct. de la permutation interdite */ TESTCALLOC(pvi,n-1,struct ValInterdit); pvi--; i = 0; for (; *s; s++) if (*s != CARBARRE && ctoelem(*s) != n) { Elem j; /* indice des predecesseurs de i */ i++; /* initialisation de P(i) */ (pvi + i)->elem = (Elem) ctoelem(*s); (pvi + i)->elemtst = 0; (pvi + i)->diffneg.inconnu = VRAI; (pvi + i)->diffpos.inconnu = VRAI; /* calcul des differences */ for (j = 1; j < i; j++) calc1diff(pvi+i,pvi+j,j); } return(pvi); } /*****************************************************************************/ /* calcul des differences entre 2 elements d'une permutation interdite */ /*****************************************************************************/ Void calc1diff(pvid,pvis,isrc) P_ValInterdit pvid; /* pointe sur element destinataire permutation interdite */ P_ValInterdit pvis; /* pointe sur element source de la permutation interdite */ Elem isrc; /* indice de l'element source */ { Short v; /* difference entre les deux elements */ v = ((Short) pvid->elem) - ((Short) pvis->elem); if (v < 0) { if (pvid->diffneg.inconnu) { pvid->diffneg.inconnu = FAUX; pvid->diffneg.val = v; pvid->diffneg.ind = isrc; } else if (pvid->diffneg.val < v) { pvid->diffneg.val = v; pvid->diffneg.ind = isrc; } } else { if (pvid->diffpos.inconnu) { pvid->diffpos.inconnu = FAUX; pvid->diffpos.val = v; pvid->diffpos.ind = isrc; } else if (pvid->diffpos.val > v) { pvid->diffpos.val = v; pvid->diffpos.ind = isrc; } } } /*****************************************************************************/ /* insertion d'1 sommet correspondant a une nouvelle permutation sur [n] */ /*****************************************************************************/ P_Sommet cree1sommet(n,site,rac) Elem n; /* dimension de la permutation */ Elem site; /* site d'insertion de l'element // permutation de son pere */ P_Racine rac; /* racine de l'arbre */ { P_Sommet p; /* pointe sur la nouvelle permutation */ TESTMALLOC(p,struct Sommet); p->n = n; p->perm = n ? cree1perm(n) : NULL; inibool8(p->sitesactifs,FAUX); p->nbfils = 0; if (sortuser[sortreel[I_SORTREEL_SIG].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbsig = calcsig(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_SID].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbsid = calcsid(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_SSG].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbssg = calcssg(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_SSD].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbssd = calcssd(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_M].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbm = calcm(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_MI].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbmi = calcmi(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_ESL].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbesl = calcesl(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_ESS].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbess = calcess(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_I_1N].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbii_1n = calcii_1n(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_I_11].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbii_11 = calcii_11(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_IN].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbiin = calciin(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_I1].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbii1 = calcii1(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_CNB].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbcnb = calccnb(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_CLG].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbclg = calcclg(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_POINTSFIXES].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbpf = calcpf(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_INVERSIONS].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbinv = calcinv(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_MAJ].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbmaj = calcmaj(adrperm(n),n); if (sortuser[sortreel[I_SORTREEL_MAJI].refuser].dde || sortuser[sortreel[I_SORTREEL_TTESSTATS].refuser].dde) p->nbmaji = calcmaji(adrperm(n),n); p->site = site; p->filsaine = NULL; p->suiv = NULL; rac->nbperm++; return(p); } /*****************************************************************************/ /* cree et affecte une nouvelle permutation sur [n] */ /*****************************************************************************/ P_Elem cree1perm(n) Elem n; /* dimension de la permutation */ { P_Elem perm; /* pointe sur la nouvelle permutation */ Elem i; /* indice de perm[] */ TESTCALLOC(perm,n,Elem); perm--; for (i = 1; i <= n; i++) perm[i] = PERM(n,i); return(perm); } /*****************************************************************************/ /* indique si la permutation est une involution sur [n] */ /*****************************************************************************/ Booleen isinvol(n) /* retourne VRAI si la permutation est une involution */ Elem n; /* dimension de la permutation */ { Booleen estinvol; /* indique si la permutation est une involution ou non */ Elem i; /* indice de la permutation/involution */ estinvol = VRAI; for (i = 1; i <= n && estinvol; i++) estinvol = ((PERM(n,i) == i) || (PERM(n,PERM(n,i)) == i)); return (estinvol); } /*****************************************************************************/ /* creation des racines par defaut */ /*****************************************************************************/ Void creeracinesdefaut(nmax) Short nmax; /* variable temporaire pour calculer nmax des racines */ { IndDescrip idomaine; /* indice des domaines */ for (idomaine = 0; idomaine < DIMDOMAINES; idomaine++) if (domaines[idomaine].dde) { P_Racine rac; /* racine de l'arbre a construire */ PERM(1,1) = 1; rac = cree1racine(&(domaines[idomaine].foret),nmax,1,1); if (! quetable) rac->ptr_permtete = cree1sommet(1,1,rac); } } /*****************************************************************************/ /* creation des racines de l'utilisateur */ /*****************************************************************************/ Booleen creeracinesuser(nmax,n,site) /* retourne VRAI si la racine a ete creee */ Short nmax; /* variable temporaire pour calculer nmax des racines */ Elem n; /* nombre d'elements de la permutation sur [n] */ Elem site; /* site d'insertion de n sur la permutation [n-1] */ { Booleen aumoins1creee; /* indique si 1 racine a ete creee */ IndDescrip idomaine; /* indice des domaines */ aumoins1creee = FAUX; for (idomaine = 0; idomaine < DIMDOMAINES; idomaine++) if (domaines[idomaine].dde) if ((! domaines[idomaine].invol) || isinvol(n)) { P_Racine rac; /* racine de l'arbre a construire */ rac = cree1racine (&(domaines[idomaine].foret),nmax,n,site); if (! quetable) rac->ptr_permtete = cree1sommet(n,site,rac); aumoins1creee = VRAI; } return(aumoins1creee); } /*****************************************************************************/ /* creation d'une racine, en append de la liste des racines des permutations */ /*****************************************************************************/ P_Racine cree1racine(p_foret,nmax,n,site) PP_Racine p_foret; /* pointe sur la foret a laquelle ajouter la racine */ Short nmax; /* valeur maximale des dimensions des permutations */ Elem n; /* dimension de la permutation de tete */ Elem site; /* site d'insertion de l'element n // permutation du pere de tete */ { P_Racine rac; /* racine de l'arbre a construire */ P_Racine rprec,rcrte; /* racines precedente, courante recherchees pour ajout */ TESTMALLOC(rac,struct Racine); /* initialisation des valeurs */ rac->ptr_permtete = NULL; rac->nmax = (Elem) (nmax < 0 ? (- nmax) : (n ? MIN(NMAX,n+nmax) : MIN(NMAX,1+nmax))); rac->n_tete = n; rac->site_tete = site; rac->perm_tete = cree1perm(rac->n_tete); rac->nbperm = (Resultat) 0; /* ajout de la nouvelle racine en fin de la liste chainee des racines */ rprec = NULL; rcrte = *p_foret; while (rcrte != NULL) { rprec = rcrte; rcrte = rcrte->suiv; } if (rprec == NULL) *p_foret = rac; else rprec->suiv = rac; rac->suiv = NULL; return(rac); } /*****************************************************************************/ /* initialisation de quetable */ /*****************************************************************************/ Void initquetable() { quetable = FAUX; if (domaines[I_DOM_PERM].dde && sortuser[I_SORTUSER_TABLE].dde) { IndDescrip idomaine; /* indice des domaines */ quetable = VRAI; for (idomaine = 0; idomaine < DIMDOMAINES && quetable; idomaine++) if (idomaine != I_DOM_PERM) if (domaines[idomaine].dde) quetable = FAUX; if (quetable) { IndDescrip isortuser; /* indice de sorties utilisateur */ for (isortuser = 0; isortuser < DIMSORTUSER && quetable; isortuser++) if (isortuser != I_SORTUSER_TABLE) if (sortuser[isortuser].dde) quetable = FAUX; } } } /*****************************************************************************/ /* edite la ligne de commande */ /*****************************************************************************/ Void edligcde(argc,argv) Int argc; /* nombre d'arguments de la ligne de commande */ P_Char argv[]; /* chaines de caracteres contenant les arguments */ { affligcde(stdout,argc,argv); if (nomfout == NULL) { IndDescrip isortuser; /* indice de sorties utilisateur */ printf("\tNom du(des) fichier(s) genere(s) :"); for (isortuser = 0; isortuser < DIMSORTUSER; isortuser++) if (sortuser[isortuser].dde) { printf("\n\t\t%s",sortuser[isortuser].nomf); if (isortuser != I_SORTUSER_CABRI) { FOPEN(fout,sortuser[isortuser].nomf); affligcde(fout,argc,argv); FCLOSE(fout); } } printf("\n"); } else { printf("\tNom du fichier en sortie : %s\n",nomfout); if (fout != stdout) { FOPEN(fout,nomfout); affligcde(fout,argc,argv); FCLOSE(fout); } } } /*****************************************************************************/ /* affiche la ligne de commande */ /*****************************************************************************/ Void affligcde(fic,argc,argv) P_FILE fic; /* fichier en sortie */ Int argc; /* nombre d'arguments de la ligne de commande */ P_Char argv[]; /* chaines de caracteres contenant les arguments */ { IndDescrip idomaine; /* indice des domaines */ IndDescrip isortuser; /* indice de sorties utilisateur */ Int iargv; /* indice de argv[] */ Booleen separracaff; /* indique si on a affiche SEPRAC ou SEPRACCUM */ separracaff = FAUX; if (fic == stdout) fprintf(fic,"\n"); fprintf(fic,"Commande : %s ",nompg); for (idomaine = 0; idomaine < DIMDOMAINES; idomaine++) if (domaines[idomaine].dde) fprintf(fic,"%c",domaines[idomaine].carrepr); fprintf(fic," "); for (isortuser = 0; isortuser < DIMSORTUSER; isortuser++) if (sortuser[isortuser].dde) fprintf(fic,"%c",sortuser[isortuser].carrepr); for (iargv = 3; iargv < argc && strcmp(SEPFIC,argv[iargv]); iargv++) if (strcmp(SEPRAC,argv[iargv]) && strcmp(SEPRACCUM,argv[iargv])) fprintf(fic," %s",argv[iargv]); else if (! separracaff) { fprintf(fic," %s",tablesacumuler ? SEPRACCUM : SEPRAC); separracaff = VRAI; } if (! separracaff) fprintf(fic," %s 1",tablesacumuler ? SEPRACCUM : SEPRAC); fprintf(fic," %s",SEPFIC); if (nomfout != NULL) fprintf(fic," %s",nomfout); fprintf(fic,"\n"); } /*===========================================================================*/ /* construction de l'arbre des involutions/permutations a motifs exclus */ /*===========================================================================*/ /*****************************************************************************/ /* construction successive des arbres des involutions/permutations */ /*****************************************************************************/ Void cons() { IndDescrip idomaine; /* indice des domaines */ for (idomaine = 0; idomaine < DIMDOMAINES; idomaine++) if (domaines[idomaine].dde) { if (echo) printf("\t%s\n",domaines[idomaine].txt); switch (idomaine) { case I_DOM_PERM : consperm(); break; case I_DOM_PERMALT : conspermalt(); break; case I_DOM_INVOLRECUR : consinvolrecur(); break; case I_DOM_INVOLPTFIX : consinvolptfix(); break; default : erreur(22); break; } } CFREE(wperms); } /*****************************************************************************/ /* construction successive des arbres des permutations */ /*****************************************************************************/ Void consperm() { P_Racine rac; /* racine des arbres a construire */ struct Valres valrescum; /* valeurs stockage resultats cumules */ P_Res tablecum; /* table resultats cumules par nb_fils X nb_perm. */ Indtable dimcum; /* dimension de tablecum[] */ Resultat nbpermcum; /* nombre de permutations cumulees */ Elem nmaxcum; /* dimension maximale des permutations cumulees */ if (quetable && tablesacumuler) creetablcum(domaines[I_DOM_PERM].foret,VRAI,&valrescum,&tablecum, &dimcum,&nbpermcum,&nmaxcum); for (rac = domaines[I_DOM_PERM].foret; rac != NULL; rac = rac->suiv) { if (rac->n_tete <= rac->nmax) { initwperms(rac); if (quetable) { struct Valres valres; /* valeurs stockage resultats */ P_Res table; /* table resultats nb_fils X nb_perm. */ Indtable dim; /* dimension de table[] */ if (echo) printf("\t\t%s\n", sortuser[I_SORTUSER_TABLE].txt); inittable(calcmaxnbperm(rac->n_tete,rac->nmax), rac->nmax,&valres,&table,&dim); gotperm(VRAI,rac->n_tete,NULL,rac->site_tete,rac, &valres,table); if (tablesacumuler) { nbpermcum += rac->nbperm; cumultables(tablecum,&valrescum,nmaxcum,table, &valres,rac->nmax,rac->n_tete); } else afftable(I_DOM_PERM,I_SORTREEL_TABLE, rac->n_tete,rac->nmax,table,&valres); CFREE(table); } else goperm(VRAI,rac->ptr_permtete->n,NULL, rac->ptr_permtete,rac->ptr_permtete->site, rac->ptr_permtete->sitesactifs,rac); } } if (quetable && tablesacumuler) { afftable(I_DOM_PERM,I_SORTREEL_TABLE,1,nmaxcum,tablecum,&valrescum); CFREE(tablecum); } } /*****************************************************************************/ /* construction recursive d'un arbre des permutations quetable */ /*****************************************************************************/ Void gotperm(dsarbre,n,gdpere_sitesactifs,pere_site,rac,p_valres,table) /* le traitement se fait en 2 etapes pr avoir entierement constitue */ /* la liste des sites actifs avant de lancer la recursion ; */ /* cela optimise le traitement de tstvalide() */ Booleen dsarbre; /* indique si la permutation est effectivement dans l'arbre */ Elem n; /* dimension de la permutation */ P_Bool8 gdpere_sitesactifs; /* pointe sur sites actifs permutation sur [n-1] */ Elem pere_site; /* site d'insertion de la permutation sur [n] */ P_Racine rac; /* racine de l'arbre a construire */ P_Valres p_valres; /* pointe sur les valeurs des resultats */ P_Res table; /* table des resultats */ { Bool8 pere_sitesactifs[NBBOOL8]; /* sites actifs de permutation sur [n] */ Bool8 sitesbarres[NBBOOL8]; /* sites actifs permutation sur [n] apres barres */ Elem site; /* site d'insertion de l'element n+1 dans [n] pour [n+1] */ Elem nbfils; /* nombre de fils dans [n+1] pour [n] */ /* mise a jour du nombre total de permutations de l'arbre et initialisations */ if (dsarbre) { rac->nbperm++; nbfils = 0; } inibool8(pere_sitesactifs,FAUX); inibool8(sitesbarres,FAUX); /* recherche des sites actifs */ for (site = n + 1; site > 0; site--) if (tstvalide(n,site,gdpere_sitesactifs,pere_site)) { mvbool8(pere_sitesactifs,site,VRAI); if (tstbarrvalide(n,site)) { mvbool8(sitesbarres,site,VRAI); if (dsarbre) nbfils++; } } if (dsarbre) incresultat(p_valres,table+indtable(rac->nmax,p_valres,INDICVAL,n, nbfils)); /* recursion sur les fils actifs */ if (n < rac->nmax) for (site = cpperm(n); tstperm(site); mvperm(n+1,&site)) if (tstbool8(pere_sitesactifs,site) && (n + 1 != rac->nmax || tstbool8(sitesbarres,site))) { if (tstbool8(sitesbarres,site) && ! dsarbre) creeracdom(I_DOM_PERM,rac->nmax,n+1,site); gotperm(tstbool8(sitesbarres,site),n+1, pere_sitesactifs,site,rac,p_valres,table); } } /*****************************************************************************/ /* construction recursive d'un arbre des permutations */ /*****************************************************************************/ Void goperm(dsarbre,n,gdpere_sitesactifs,pere,pere_site,pere_sitesactifs,rac) /* le traitement se fait en 2 etapes pr avoir entierement constitue */ /* la liste des sites actifs avant de lancer la recursion ; */ /* cela optimise le traitement de tstvalide() */ Booleen dsarbre; /* indique si la permutation est effectivement dans l'arbre */ Elem n; /* dimension de la permutation */ P_Bool8 gdpere_sitesactifs; /* pointe sur sites actifs permutation sur [n-1] */ P_Sommet pere; /* pointe sur la permutation sur [n] */ Elem pere_site; /* site d'insertion de la permutation sur [n] */ P_Bool8 pere_sitesactifs; /* pointe sur sites actifs permutation sur [n] */ P_Racine rac; /* racine de l'arbre a construire */ { Elem site; /* site d'insertion de l'element n+1 dans [n] pour [n+1] */ Bool8 sitesbarres[NBBOOL8]; /* sites actifs permutation sur [n] apres barres */ /* recherche des sites actifs */ inibool8(sitesbarres,FAUX); for (site = n + 1; site > 0; site--) if (tstvalide(n,site,gdpere_sitesactifs,pere_site)) { mvbool8(pere_sitesactifs,site,VRAI); if (tstbarrvalide(n,site)) { mvbool8(sitesbarres,site,VRAI); if (dsarbre) pere->nbfils++; } } /* recursion sur les fils actifs */ if (n < rac->nmax) for (site = cpperm(n); tstperm(site); mvperm(n+1,&site)) if (tstbool8(pere_sitesactifs,site) && (n + 1 != rac->nmax || tstbool8(sitesbarres,site))) if (tstbool8(sitesbarres,site)) if (dsarbre) { /* pointe sur permutation fils [n+1] */ P_Sommet fils; /* nouveau fils cree tete liste fils */ fils = cree1sommet(n+1,site,rac); fils->suiv = pere->filsaine; pere->filsaine = fils; goperm(VRAI,n+1,pere_sitesactifs,fils, fils->site,fils->sitesactifs, rac); } else creeracdom(I_DOM_PERM,rac->nmax,n+1, site); else { /* sites actifs perm. d'un "fils" hors arbre */ Bool8 fils_sitesactifs[NBBOOL8]; inibool8(fils_sitesactifs,FAUX); goperm(FAUX,n+1,pere_sitesactifs,NULL,site, fils_sitesactifs,rac); } /* mise a jour eventuelle des sites actifs de la permutation sur [n] */ if (lstbarre != NULL) cpbool8(pere_sitesactifs,sitesbarres); } /*****************************************************************************/ /* construction successive des arbres des permutations alternantes */ /*****************************************************************************/ Void conspermalt() { P_Racine rac; /* racine des arbres a construire */ for (rac = domaines[I_DOM_PERMALT].foret; rac != NULL; rac = rac->suiv) { if (rac->n_tete <= rac->nmax) { initwperms(rac); gopermalt(VRAI,rac->ptr_permtete->n,rac->ptr_permtete,rac); } } } /*****************************************************************************/ /* construction recursive d'un arbre des permutations alternantes */ /*****************************************************************************/ Void gopermalt(dsarbre,n,pere,rac) Booleen dsarbre; /* indique si la permutation est effectivement dans l'arbre */ Elem n; /* dimension de la permutation */ P_Sommet pere; /* pointe sur la permutation sur [n] */ P_Racine rac; /* racine de l'arbre a construire */ { Elem site; /* element ajoute en derniere position */ Elem siteinf; /* borne inferieure pour site */ Elem sitesup; /* borne superieure pour site */ P_Elem perminv; /* permutation inverse sur [n] */ perminv = inverseperm(adrperm(n),n); inipermalt(n); if (ISIMPAIR(n)) { siteinf = PERM(n,n) + 1; sitesup = n + 1; } else { siteinf = 1; sitesup = PERM(n,n); } for (site = sitesup; site >= siteinf; site--) { Booleen valide; /* indique si permutation est valide ou non */ if (site < sitesup) { PERM(n+1,n+1) --; PERM(n+1,perminv[site]) ++; } valide = tstracine(n+1); if (valide && dsarbre) { pere->nbfils++; mvbool8(pere->sitesactifs,site,VRAI); } if (n < rac->nmax) if (valide) if (dsarbre) gopermalt(VRAI,n+1,ajoutfils(pere,n+1,site,rac) ,rac); else creeracdom(I_DOM_PERMALT,rac->nmax,n+1,site); else gopermalt(FAUX,n+1,NULL,rac); } CFREE(perminv+1); } /*****************************************************************************/ /* construction successive des arbres des involutions (recurrence) */ /*****************************************************************************/ Void consinvolrecur() { P_Racine rac; /* racine des arbres a construire */ for (rac = domaines[I_DOM_INVOLRECUR].foret; rac != NULL; rac = rac->suiv) { if (rac->n_tete <= rac->nmax) { initwperms(rac); goinvolrecur(VRAI,rac->ptr_permtete->n,rac->ptr_permtete,rac); } } } /*****************************************************************************/ /* construction recursive d'un arbre des involutions (recurrence) */ /*****************************************************************************/ Void goinvolrecur(dsarbre,n,pere,rac) Booleen dsarbre; /* indique si la permutation est effectivement dans l'arbre */ Elem n; /* dimension de la permutation */ P_Sommet pere; /* pointe sur la permutation sur [n] */ P_Racine rac; /* racine de l'arbre a construire */ { Elem site; /* site d'echange d'un point fixe de [n] avec (n+1) */ Elem siteinf; /* site inferieur */ siteinf = (PERM(n,n) == n ? 0 : n); for (site = cpperm(n); site > siteinf; site--) { Booleen valide; /* indique si permutation est valide ou non */ if (site < n + 1) { if (PERM(n+1,site) == site) PERM(n+1,site+1) = site + 1; else { Elem svg; /* (svg,site) est un cycle de lg 2 */ svg = PERM(n+1,site); PERM(n+1,site+1) = svg; PERM(n+1,svg) = site + 1; } PERM(n+1,site) = n + 1; PERM(n+1,n+1) --; } valide = tstracine(n+1); if (valide && dsarbre) { pere->nbfils++; mvbool8(pere->sitesactifs,site,VRAI); } if (n < rac->nmax) if (valide) if (dsarbre) goinvolrecur(VRAI,n+1,ajoutfils(pere,n+1,site, rac),rac); else creeracdom(I_DOM_INVOLRECUR,rac->nmax,n+1, site); else goinvolrecur(FAUX,n+1,NULL,rac); } } /*****************************************************************************/ /* construction successive des arbres des involutions (point fixe) */ /*****************************************************************************/ Void consinvolptfix() { P_Racine rac; /* racine des arbres a construire */ for (rac = domaines[I_DOM_INVOLPTFIX].foret; rac != NULL; rac = rac->suiv) { if (rac->n_tete <= rac->nmax) { initwperms(rac); goinvolptfix(VRAI,rac->ptr_permtete->n,rac->ptr_permtete,rac); } } } /*****************************************************************************/ /* construction recursive d'un arbre des involutions (point fixe) */ /*****************************************************************************/ Void goinvolptfix(dsarbre,n,pere,rac) Booleen dsarbre; /* indique si la permutation est effectivement dans l'arbre */ Elem n; /* dimension de la permutation */ P_Sommet pere; /* pointe sur la permutation sur [n] */ P_Racine rac; /* racine de l'arbre a construire */ { Elem site; /* site d'echange d'un point fixe de [n] avec (n+1) */ for (site = cpperm(n); site > 0; site--) if (site == n + 1 || PERM(n,site) == site) { Booleen valide; /* indique si permutation est valide ou non */ echpfperm(n+1,site); valide = tstracine(n+1); if (valide && dsarbre) { pere->nbfils++; mvbool8(pere->sitesactifs,site,VRAI); } if (n < rac->nmax) if (valide) if (dsarbre) goinvolptfix(VRAI,n+1,ajoutfils(pere, n+1,site,rac),rac); else creeracdom(I_DOM_INVOLPTFIX,rac->nmax, n+1,site); else goinvolptfix(FAUX,n+1,NULL,rac); } } /*****************************************************************************/ /* ajoute un fils en tete de la liste des fils */ /*****************************************************************************/ P_Sommet ajoutfils(pere,n,site,rac) P_Sommet pere; /* pointe sur la permutation pere sur [n-1] */ Elem n; /* dimension de la permutation fils */ Elem site; /* site d'insertion */ P_Racine rac; /* racine de l'arbre a construire */ { P_Sommet fils; /* pointe sur la permutation fils sur [n] */ fils = cree1sommet(n,site,rac); fils->suiv = pere->filsaine; pere->filsaine = fils; return(fils); } /*****************************************************************************/ /* cree une nouvelle racine pour un domaine precis */ /*****************************************************************************/ Void creeracdom(idomaine,nmax,n,site) IndDescrip idomaine; /* indice des domaines */ Short nmax; /* n maximum de la racine */ Elem n; /* dimension de la permutation fils */ Elem site; /* site d'insertion */ { P_Racine newrac; /* pointe sur la nouvelle racine */ newrac = cree1racine(&(domaines[idomaine].foret),-nmax,n,site); newrac->ptr_permtete = cree1sommet(n,site,newrac); } /*****************************************************************************/ /* teste si la racine proposee par l'utilisateur est valide ou non */ /*****************************************************************************/ Booleen tstracine(n) Elem n; /* nombre d'elements de la permutation */ { P_Interdit pi; /* pointe successivement sur une permutation interdite */ P_Barre pib; /* pointe successivement sur une permutation interdite barree */ for (pi = lstinterdit; pi != NULL; pi = pi->suiv) if (! tstdiff1(1,n,pi->n_suiv,pi->valeurs_suiv,0)) return(FAUX); for (pib = lstbarre; pib != NULL; pib = pib->suiv) if (! tst1barre(n,pib)) return(FAUX); return(VRAI); } /*****************************************************************************/ /* teste si la permutation sur [n+1] est valide (ou interdite) */ /*****************************************************************************/ Booleen tstvalide(n,site,gdpere_sitesactifs,pere_site) /* retourne FAUX si contient la sous-sequence interdite */ Elem n; /* dimension de la permutation */ Elem site; /* site d'insertion de l'element n+1 dans la permutation sur [n] */ P_Bool8 gdpere_sitesactifs; /* pointe sur sites actifs permutation sur [n-1] */ Elem pere_site; /* site de n dans la permutation sur [n-1] */ { P_Interdit pi; /* pointe successivement sur une permutation interdite */ /* teste si le site n'a pas deja ete interdit pour le grand-pere */ if (gdpere_sitesactifs != NULL) { Elem site_suiv; /* site suppose interdit sur [n-1] */ site_suiv = (site > pere_site) ? (site - 1) : site; if ( /* site_suiv != pere_site && */ ! tstbool8(gdpere_sitesactifs,site_suiv)) return(FAUX); } /* teste successivement les permutations interdites */ for (pi = lstinterdit; pi != NULL; pi = pi->suiv) if (! tst1interdit(n,site,pere_site,pi,gdpere_sitesactifs==NULL)) return(FAUX); /* en dernier ressort, l'insertion est valide */ return(VRAI); } /*****************************************************************************/ /* teste si une permutation interdit la permutation sur [n+1] */ /*****************************************************************************/ Booleen tst1interdit(n,site,pere_site,pi,estracine) /* retourne FAUX si contient la sous-sequence interdite */ Elem n; /* dimension de la permutation */ Elem site; /* site d'insertion de l'element n+1 dans la permutation sur [n] */ Elem pere_site; /* site d'insertion de l'element n ds permutation sur [n-1] */ P_Interdit pi; /* pointe sur la permutation interdite */ Booleen estracine; /* indique si la permutation a tester est une racine */ { if (estracine) { if (site < pi->site || n + pi->site < pi->n + site) return(VRAI); return(tstdiff2(1,n,site,pi->n,pi->site,pi->valeurs,0)); } else { Elem site_suiv; /* site theorique de n+1 dans [n-1] */ if ((site <= pere_site && pi->site > pi->site_prec) || (site > pere_site && pi->site <= pi->site_prec)) return(VRAI); if ((site <= pere_site && (site < pi->site || pere_site + pi->site < pi->site_prec + site || n + pi->site_prec < pi->n + pere_site)) || (site > pere_site && (pere_site < pi->site_prec || site + pi->site_prec < pi->site + pere_site || n + pi->site < pi->n + site))) return(VRAI); site_suiv = (site > pere_site) ? (site - 1) : site; return(tstdiff3(1,n-1,MIN(pere_site,site_suiv), MAX(pere_site,site_suiv), pi->n_prec,MIN(pi->site_prec,pi->site_suiv), MAX(pi->site_prec,pi->site_suiv),pi->valeurs_prec,0)); } } /*****************************************************************************/ /* teste si la permutation barree sur [n+1] est valide (ou interdite) */ /*****************************************************************************/ Booleen tstbarrvalide(n,site) /* retourne FAUX si contient une sous-sequence barree interdite */ Elem n; /* dimension de la permutation */ Elem site; /* site d'insertion de l'element n+1 dans la permutation sur [n] */ { P_Barre pib; /* pointe successivement sur une permutation interdite barree */ if (lstbarre == NULL) return(VRAI); /* cree la permutation sur [n+1] */ cppermsite(n,site); /* teste successivement les permutations interdites barrees */ for (pib = lstbarre; pib != NULL; pib = pib->suiv) if (! tst1barre(n+1,pib)) return(FAUX); /* en dernier ressort, l'insertion est valide */ return(VRAI); } /*****************************************************************************/ /* teste si une permutation barree interdit la permutation sur [n] */ /*****************************************************************************/ Booleen tst1barre(n,pib) /* retourne FAUX si contient la permutation interdite barree */ Elem n; /* dimension de la permutation */ P_Barre pib; /* pointe sur la permutation interdite barree */ { if (n < pib->nnonbarre) return(VRAI); return(tstdiffbarre(1,n,pib->nnonbarre,pib->valnonbarre,0,pib)); } /*****************************************************************************/ /* teste recursivement si la permutation est interdite pour "barree" */ /*****************************************************************************/ Booleen tstdiffbarre(i,n,pi_n,pi_vals,pos,pib) /* retourne FAUX si contient la sous-sequence interdite barree */ Elem i; /* niveau de recursion dans la recherche */ Elem n; /* dimension de la permutation */ Elem pi_n; /* dimension de la permutation interdite (elements non barres) */ P_ValInterdit pi_vals; /* pointe sur differences de permutation interdite */ Elem pos; /* position du (i-1)eme element choisi */ P_Barre pib; /* pointe sur la permutation interdite barree */ { Elem j; /* indices possibles pour choisir le (i)eme element */ P_ValInterdit pvi; /* pointe (i)emes differences de permutation interdite */ /* fin de la recursion */ if (i > pi_n) { Elem iinonb; /* indice de inonbarre[] */ pib->ielemtst[i] = n + 1; /* teste si suffisamment de place pour placer elements pr barres */ for (iinonb = 0; iinonb <= pib->nnonbarre; iinonb++) if (pib->ielemtst[iinonb+1] + pib->inonbarre[iinonb] < pib->inonbarre[iinonb+1] + pib->ielemtst[iinonb]) return(FAUX); /* recherche des elements en correspondance avec ceux barres */ for (iinonb = 1; iinonb <= pib->nnonbarre; iinonb++) (pib->valeurs + pib->inonbarre[iinonb])->elemtst = (pib->valnonbarre + iinonb)->elemtst; return(tstdiffttbarre(1,n,pib->n,0,0,pib->valeurs,0,pib)); } /* initialisation */ pvi = pi_vals + i; /* recherche de la permutation interdite barree sans les elements barres */ for (j = pos + 1; j + pi_n <= n + i; j++) if (tst1diff(n,j,pi_n,pi_vals,pvi)) { pvi->elemtst = PERM(n,j); pib->ielemtst[i] = j; if (! tstdiffbarre(i+1,n,pi_n,pi_vals,j,pib)) return(FAUX); } /* on ne peut pas trouver de j : la sous-sequence n'existe pas */ return(VRAI); } /*****************************************************************************/ /* teste recursivement si la permutation barree complete est interdite */ /*****************************************************************************/ Booleen tstdiffttbarre(i,n,pi_n,iinonb,idsbarres,pi_vals,pos,pib) /* retourne FAUX si non contient la ss-seq interdite barree complete */ Elem i; /* niveau de recursion dans la recherche */ Elem n; /* dimension de la permutation */ Elem pi_n; /* dimension de la permutation interdite */ Elem iinonb; /* indice de pib->inonbarre[] */ Elem idsbarres; /* indice d'un element de [n] relie a un element barre */ P_ValInterdit pi_vals; /* pointe sur differences de permutation interdite */ Elem pos; /* position du (i-1)eme element choisi */ P_Barre pib; /* pointe sur la permutation interdite barree */ { Elem j; /* indices possibles pour choisir le (i)eme element */ Elem jdeb, jfin; /* bornes de debut et de fin pour j */ P_ValInterdit pvi; /* pointe (i)emes differences de permutation interdite */ /* fin de la recursion */ if (i > pi_n) return(VRAI); /* initialisations */ if (tstbool8(pib->isbarre,i)) { idsbarres++; jdeb = pos + 1; jfin = pib->ielemtst[iinonb+1] + idsbarres + pib->inonbarre[iinonb]; jfin -= pib->inonbarre[iinonb+1]; } else { idsbarres = 0; iinonb++; jdeb = pib->ielemtst[iinonb]; jfin = jdeb; } pvi = pi_vals + i; /* recherche de la sous-sequence interdite */ for (j = jdeb; j <= jfin; j++) if (tst1diff(n,j,pi_n,pi_vals,pvi)) { pvi->elemtst = PERM(n,j); if (tstdiffttbarre(i+1,n,pi_n,iinonb,idsbarres,pi_vals,j,pib)) return(VRAI); } /* on ne peut pas trouver de j : la sous-sequence barree n'existe pas */ return(FAUX); } /*****************************************************************************/ /* teste recursivement si la permutation est interdite, en 1 tranche */ /*****************************************************************************/ Booleen tstdiff1(i,n,pi_n,pi_vals,pos) /* retourne FAUX si contient la sous-sequence interdite */ Elem i; /* niveau de recursion dans la recherche */ Elem n; /* dimension de la permutation */ Elem pi_n; /* dimension de la permutation interdite */ P_ValInterdit pi_vals; /* pointe sur differences de permutation interdite */ Elem pos; /* position du (i-1)eme element choisi */ { Elem j; /* indices possibles pour choisir le (i)eme element */ P_ValInterdit pvi; /* pointe (i)emes differences de permutation interdite */ /* fin de la recursion */ if (i > pi_n) return(FAUX); /* initialisation */ pvi = pi_vals + i; /* recherche de la sous-sequence interdite */ for (j = pos + 1; j + pi_n <= n + i; j++) if (tst1diff(n,j,pi_n,pi_vals,pvi)) { pvi->elemtst = PERM(n,j); if (! tstdiff1(i+1,n,pi_n,pi_vals,j)) return(FAUX); } /* on ne peut pas trouver de j : la sous-sequence n'existe pas */ return(VRAI); } /*****************************************************************************/ /* teste recursivement si permutation est interdite, separee en 2 tranches */ /*****************************************************************************/ Booleen tstdiff2(i,n,site,pi_n,pi_site,pi_vals,pos) /* retourne FAUX si contient la sous-sequence interdite */ Elem i; /* niveau de recursion dans la recherche */ Elem n; /* dimension de la permutation */ Elem site; /* site d'insertion de l'element n+1 dans la permutation sur [n] */ /* == min_p , indice de la permutation debut de la 2eme tranche */ Elem pi_n; /* dimension de la permutation interdite */ Elem pi_site; /* site d'insertion pi_n+1 dans permutation interdite [pi_n] */ /* == min_pi , indice permutation interdite debut 2eme tranche */ P_ValInterdit pi_vals; /* pointe sur differences de permutation interdite */ Elem pos; /* position du (i-1)eme element choisi */ { Elem j; /* indices possibles pour choisir le (i)eme element */ Elem jdeb, jfin; /* bornes de debut et de fin pour j */ P_ValInterdit pvi; /* pointe (i)emes differences de permutation interdite */ /* fin de la recursion */ if (i > pi_n) return(FAUX); /* initialisations */ if (i < pi_site) { jdeb = pos + 1; jfin = site + i; jfin -= pi_site; } else { jdeb = (i == pi_site) ? site : (pos + 1); jfin = n + i; jfin -= pi_n; } pvi = pi_vals + i; /* recherche de la sous-sequence interdite */ for (j = jdeb; j <= jfin; j++) if (tst1diff(n,j,pi_n,pi_vals,pvi)) { pvi->elemtst = PERM(n,j); if (! tstdiff2(i+1,n,site,pi_n,pi_site,pi_vals,j)) return(FAUX); } /* on ne peut pas trouver de j : la sous-sequence n'existe pas */ return(VRAI); } /*****************************************************************************/ /* teste recursivement si permutation est interdite, separee en 3 tranches */ /*****************************************************************************/ Booleen tstdiff3(i,n,min_p,max_p,pi_n,min_pi,max_pi,pi_vals,pos) /* retourne FAUX si contient la sous-sequence interdite */ Elem i; /* niveau de recursion dans la recherche */ Elem n; /* dimension de la permutation */ Elem min_p; /* indice de la permutation du debut de la 2eme tranche */ Elem max_p; /* indice de la permutation du debut de la 3eme tranche */ Elem pi_n; /* dimension de la permutation interdite */ Elem min_pi; /* indice de la permutation interdite debut de la 2eme tranche */ Elem max_pi; /* indice de la permutation interdite debut de la 3eme tranche */ P_ValInterdit pi_vals; /* pointe sur differences de permutation interdite */ Elem pos; /* position du (i-1)eme element choisi */ { Elem j; /* indices possibles pour choisir le (i)eme element */ Elem jdeb, jfin; /* bornes de debut et de fin pour j */ P_ValInterdit pvi; /* pointe (i)emes differences de permutation interdite */ /* fin de la recursion */ if (i > pi_n) return(FAUX); /* initialisations */ if (i < min_pi) { jdeb = pos + 1; jfin = min_p + i; jfin -= min_pi; } else if (i < max_pi) { jdeb = (i == min_pi) ? min_p : (pos + 1); jfin = max_p + i; jfin -= max_pi; } else { jdeb = (i == max_pi) ? max_p : (pos + 1); jfin = n + i; jfin -= pi_n; } pvi = pi_vals + i; /* recherche de la sous-sequence interdite */ for (j = jdeb; j <= jfin; j++) if (tst1diff(n,j,pi_n,pi_vals,pvi)) { pvi->elemtst = PERM(n,j); if (! tstdiff3(i+1,n,min_p,max_p,pi_n,min_pi,max_pi,pi_vals,j)) return(FAUX); } /* on ne peut pas trouver de j : la sous-sequence n'existe pas */ return(VRAI); } /*****************************************************************************/ /* teste si l'indice est possible comparee a la permutation interdite */ /*****************************************************************************/ Booleen tst1diff(n,j,pi_n,pi_vals,pvi) Elem n; /* dimension de la permutation */ Elem j; /* indice a tester pour choisir le (i)eme element */ Elem pi_n; /* dimension de la permutation interdite */ P_ValInterdit pi_vals; /* pointe sur differences de permutation interdite */ P_ValInterdit pvi; /* pointe (i)emes differences de permutation interdite */ { return(((pvi->diffpos.inconnu && PERM(n,j) >= pvi->elem) || ((! pvi->diffpos.inconnu) && PERM(n,j) >= (pi_vals + pvi->diffpos.ind)->elemtst + pvi->diffpos.val)) && ((pvi->diffneg.inconnu && PERM(n,j) + pi_n <= n + pvi->elem) || ((! pvi->diffneg.inconnu) && PERM(n,j) <= (pi_vals + pvi->diffneg.ind)->elemtst + pvi->diffneg.val))); } /*===========================================================================*/ /* gestion de la table wperms[] */ /*===========================================================================*/ /*****************************************************************************/ /* calcul de la dimension maximale de wperms[] */ /*****************************************************************************/ Int calcdimwperms(nmax) Int nmax; /* nombre maximum des permutations sur [nmax] */ /* < 0 si '+' absent, >= 0 si '+' present */ { Int nmaxwp; /* dimension maximale de wperms[] */ nmaxwp = nmax < 0 ? (- nmax) : NMAX; nmaxwp ++; return((nmaxwp * (nmaxwp + 1)) / 2 ); } /*****************************************************************************/ /* initialise le tableau contenant les permutations successivement testees */ /*****************************************************************************/ Void initwperms(rac) P_Racine rac; /* racine de l'arbre a construire */ { Elem i; if (! quetable) if (rac->ptr_permtete == NULL) erreur(9); if (rac->perm_tete == NULL) erreur(9); for (i = 1; i <= rac->n_tete; i++) PERM(rac->n_tete,i) = rac->perm_tete[i]; iniperm(rac->n_tete); } /*****************************************************************************/ /* recopie recursivement [n] dans [n-1] .. [1] */ /*****************************************************************************/ Void iniperm(n) Elem n; /* dimension de la permutation */ { if (n > 1) { Elem i; /* indice de la permutation */ Elem j; /* indice de la permutation */ j = 1; for (i = 1; i <= n; i++) if (PERM(n,i) != n) { PERM(n-1,j) = PERM(n,i); j++; } iniperm(n-1); } } /*****************************************************************************/ /* initialisation de permutation alternante sur [n+1] a partir celle sur [n] */ /*****************************************************************************/ Void inipermalt(n) Elem n; /* dimension de la permutation */ { if (ISIMPAIR(n)) { Elem i; /* indice de la permutation */ for (i = 1; i <= n; i++) PERM(n+1,i) = PERM(n,i); PERM(n+1,n+1) = n + 1; } else { Elem i; /* indice de la permutation */ for (i = 1; i <= n; i++) PERM(n+1,i) = (PERM(n,i) >= PERM(n,n) ? PERM(n,i) + 1 : PERM(n,i)); PERM(n+1,n+1) = PERM(n,n); } } /*****************************************************************************/ /* recopie de [n] dans [n+1] et insertion de n+1 en site */ /*****************************************************************************/ Void cppermsite(n,site) Elem n; /* dimension de la permutation */ Elem site; /* site d'insertion de n+1 dans [n] */ { Elem i; /* indice de la permutation */ for (i = 1; i <= n + 1; i++) if (i == site) PERM(n+1,i) = n + 1; else PERM(n+1,i) = PERM(n,i < site ? i : (i - 1)); } /*****************************************************************************/ /* recopie de [n] dans [n+1] et insertion de n+1 en fin */ /*****************************************************************************/ Elem cpperm(n) Elem n; /* dimension de la permutation */ { Elem i; /* indice de la permutation */ for (i = 1; i <= n; i++) PERM(n+1,i) = PERM(n,i); PERM(n+1,n+1) = n + 1; return(n+1); } /*****************************************************************************/ /* deplace le site de [n] d'une case vers la gauche */ /*****************************************************************************/ Void mvperm(n,p_site) Elem n; /* dimension de la permutation */ P_Elem p_site; /* site d'insertion de l'element */ { (*p_site)--; if (tstperm(*p_site)) { PERM(n,*p_site+1) = PERM(n,*p_site); PERM(n,*p_site) = n; } } /*****************************************************************************/ /* teste la fin du deplacement de la permutation */ /*****************************************************************************/ Booleen tstperm(site) Elem site; /* site d'insertion de l'element */ { return(site > 0); } /*****************************************************************************/ /* echange l'ancien point fixe de la permutation avec le nouveau */ /*****************************************************************************/ Void echpfperm(n,newpf) Elem n; /* dimension de la permutation */ Elem newpf; /* nouveau point fixe */ { /* ancien point fixe remis a sa place */ PERM(n,PERM(n,n)) = PERM(n,n); /* creation du nouveau cycle de longueur 2 */ PERM(n,n) = newpf; PERM(n,newpf) = n; } /*****************************************************************************/ /* retourne l'adresse de debut de la permutation sur [n] */ /*****************************************************************************/ P_Elem adrperm(n) Elem n; /* dimension de la permutation */ { return(wperms + ( ( n * ( n - 1 ) ) / 2 ) - 1); } /*****************************************************************************/ /* retourne l'indice de wperms */ /*****************************************************************************/ Indtable indwperms(n,i) Elem n; /* dimension de la permutation */ Elem i; /* indice dans la permutation */ { return((( n * ( n - 1 ) ) / 2 + i ) - 1); } /*===========================================================================*/ /* calculs sur des involutions et permutations */ /*===========================================================================*/ /*****************************************************************************/ /* calcule le nombre de points fixes d'une permutation ou involution sur [n] */ /*****************************************************************************/ Elem calcpf(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem nbptfix; /* nombre de points fixes */ Elem i; /* indice de la permutation/involution */ nbptfix = 0; for (i = 1; i <= n; i++) if (perm[i] == i) nbptfix++; return (nbptfix); } /*****************************************************************************/ /* calcule le nombre de saillants superieurs a droite d'1 perm. sur [n] */ /*****************************************************************************/ Elem calcssd(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { if (n <= 0) return (0); else { Elem nbsaillant; /* nombre d'elements saillants */ Elem saillant; /* dernier element saillant trouve */ Elem i; /* indice de la permutation */ saillant = perm[n]; nbsaillant = 1; for (i = n - 1; i > 0 && saillant < n; i--) if (perm[i] > saillant) { saillant = perm[i]; nbsaillant++; } return (nbsaillant); } } /*****************************************************************************/ /* calcule le nombre de saillants superieurs a gauche d'1 perm. sur [n] */ /*****************************************************************************/ Elem calcssg(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { if (n <= 0) return (0); else { Elem nbsaillant; /* nombre d'elements saillants */ Elem saillant; /* dernier element saillant trouve */ Elem i; /* indice de la permutation */ saillant = perm[1]; nbsaillant = 1; for (i = 2; i <= n && saillant < n; i++) if (perm[i] > saillant) { saillant = perm[i]; nbsaillant++; } return (nbsaillant); } } /*****************************************************************************/ /* calcule le nombre de saillants inferieurs a droite d'1 perm. sur [n] */ /*****************************************************************************/ Elem calcsid(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { if (n <= 0) return (0); else { Elem nbsaillant; /* nombre d'elements saillants */ Elem saillant; /* dernier element saillant trouve */ Elem i; /* indice de la permutation */ saillant = perm[n]; nbsaillant = 1; for (i = n - 1; i > 0 && saillant > 1; i--) if (perm[i] < saillant) { saillant = perm[i]; nbsaillant++; } return (nbsaillant); } } /*****************************************************************************/ /* calcule le nombre de saillants inferieurs a gauche d'1 perm. sur [n] */ /*****************************************************************************/ Elem calcsig(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { if (n <= 0) return (0); else { Elem nbsaillant; /* nombre d'elements saillants */ Elem saillant; /* dernier element saillant trouve */ Elem i; /* indice de la permutation */ saillant = perm[1]; nbsaillant = 1; for (i = 2; i <= n && saillant > 1; i++) if (perm[i] < saillant) { saillant = perm[i]; nbsaillant++; } return (nbsaillant); } } /*****************************************************************************/ /* calcule le nombre de montees d'une permutation sur [n] */ /*****************************************************************************/ Elem calcm(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem nbmontee; /* nombre de montees calculees */ Elem i; /* indice de la permutation */ nbmontee = 0; for (i = 1; i < n; i++) if (perm[i] < perm[i+1]) nbmontee++; return (nbmontee); } /*****************************************************************************/ /* calcule le nombre de descentes d'une permutation sur [n] */ /*****************************************************************************/ Elem calcd(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { return ((n - 1) - calcm(perm,n)); } /*****************************************************************************/ /* calcule le nombre de montees inverses d'une permutation sur [n] */ /*****************************************************************************/ Elem calcmi(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { P_Elem perminv; /* pointe sur la permutation inverse */ Elem nbmi; /* major de la permutation inverse */ perminv = inverseperm(perm,n); nbmi = calcm(perminv,n); CFREE(perminv+1); return (nbmi); } /*****************************************************************************/ /* calcule le nombre de montees inverses d'une permutation sur [n] v. 2 */ /*****************************************************************************/ Elem calcmi2(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem nbmi; /* nombre de montees inverses calculees */ Elem i; /* indice de la permutation */ nbmi = (perm[1] == n ? 0 : 1); for (i = 2; i < n; i++) { Booleen trouve; /* indique si on a trouve l'element */ Elem j; /* indice de la permutation */ trouve = FAUX; for (j = i + 1; j <= n && ! trouve; j++) if (perm[j] == perm[i] + 1) { trouve = VRAI; nbmi++; } } return (nbmi); } /*****************************************************************************/ /* calcule le nombre de descentes inverses d'une permutation sur [n] */ /*****************************************************************************/ Elem calcdi(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { return ((n - 1) - calcmi(perm,n)); } /*****************************************************************************/ /* calcule le nombre d'excedences superieures strictes d'1 perm. sur [n] */ /*****************************************************************************/ Elem calcess(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem nbexcedence; /* nombre d'excedences calculees */ Elem i; /* indice de la permutation */ nbexcedence = 0; for (i = 1; i <= n; i++) if (perm[i] > i) nbexcedence++; return (nbexcedence); } /*****************************************************************************/ /* calcule le nombre d'excedences inferieures strictes d'1 perm. sur [n] */ /*****************************************************************************/ Elem calceis(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { return (n - calcesl(perm,n)); } /*****************************************************************************/ /* calcule le nombre d'excedences superieures larges d'1 perm. sur [n] */ /*****************************************************************************/ Elem calcesl(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem nbexcedence; /* nombre d'excedences calculees */ Elem i; /* indice de la permutation */ nbexcedence = 0; for (i = 1; i <= n; i++) if (perm[i] >= i) nbexcedence++; return (nbexcedence); } /*****************************************************************************/ /* calcule le nombre d'excedences inferieures larges d'1 perm. sur [n] */ /*****************************************************************************/ Elem calceil(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { return (n - calcess(perm,n)); } /*****************************************************************************/ /* calcule l'indice de l'element n d'une permutation sur [n] */ /*****************************************************************************/ Elem calcii_1n(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem indice; /* indice de la permutation */ indice = 1; while (perm[indice] != n) indice++; return (indice); } /*****************************************************************************/ /* calcule l'indice de l'element 1 d'une permutation sur [n] */ /*****************************************************************************/ Elem calcii_11(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ /* INUTILISE */ { Elem indice; /* indice de la permutation */ indice = 1; while (perm[indice] != 1) indice++; return (indice); } /*****************************************************************************/ /* calcule l'element en position n d'une permutation sur [n] */ /*****************************************************************************/ Elem calciin(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { return (perm[n]); } /*****************************************************************************/ /* calcule l'element en position 1 d'une permutation sur [n] */ /*****************************************************************************/ Elem calcii1(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ /* INUTILISE */ { return (perm[1]); } /*****************************************************************************/ /* calcule le nombre de cycles d'une permutation sur [n] */ /*****************************************************************************/ Elem calccnb(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem nbcycles; /* nombre de cycles calcules */ P_Booleen vu; /* indique si l'element a deja ete vu pour un cycle precedent */ Elem i; /* indice de la permutation */ nbcycles = 0; TESTCALLOC(vu,n,Booleen); vu--; for (i = 1; i <= n; i++) vu[i] = FAUX; for (i = 1; i <= n; i++) if (! vu[i]) { Elem j; /* indice de la permutation */ nbcycles++; vu[i] = VRAI; for (j = perm[i]; j != i; j = perm[j]) vu[j] = VRAI; } CFREE(vu+1); return (nbcycles); } /*****************************************************************************/ /* calcule la longueur du plus grand cycle d'une permutation sur [n] */ /*****************************************************************************/ Elem calcclg(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { Elem lgcycle; /* longueur du + grand cycle calcule */ P_Booleen vu; /* indique si l'element a deja ete vu pour un cycle precedent */ Elem i; /* indice de la permutation */ lgcycle = 0; TESTCALLOC(vu,n,Booleen); vu--; for (i = 1; i <= n; i++) vu[i] = FAUX; for (i = 1; i <= n; i++) if (! vu[i]) { Elem j; /* indice de la permutation */ Elem l; /* calcule de la longueur de ce cycle */ l = 1; vu[i] = VRAI; for (j = perm[i]; j != i; j = perm[j]) { vu[j] = VRAI; l++; } if (l > lgcycle) lgcycle = l; } CFREE(vu+1); return (lgcycle); } /*****************************************************************************/ /* calcule le nombre d'inversions d'une permutation sur [n] */ /*****************************************************************************/ ElemGd calcinv(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { ElemGd nbinv; /* nombre d'inversions */ Elem i; /* indice de la permutation */ nbinv = 0; for (i = 1; i < n; i++) { Elem j; /* indice de la permutation */ for (j = i + 1; j <= n; j++) if (perm[i] > perm[j]) nbinv++; } return (nbinv); } /*****************************************************************************/ /* calcule le major d'une permutation sur [n] */ /*****************************************************************************/ ElemGd calcmaj(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { ElemGd major; /* major = somme des indices des descentes */ Elem i; /* indice de la permutation */ major = 0; for (i = 1; i < n; i++) if (perm[i] > perm[i+1]) major += i; return (major); } /*****************************************************************************/ /* calcule le major inverse d'une permutation sur [n] */ /*****************************************************************************/ ElemGd calcmaji(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { P_Elem perminv; /* pointe sur la permutation inverse */ ElemGd majorinv; /* major de la permutation inverse */ perminv = inverseperm(perm,n); majorinv = calcmaj(perminv,n); CFREE(perminv+1); return (majorinv); } /*****************************************************************************/ /* cree l'inverse de la permutation sur [n] */ /*****************************************************************************/ P_Elem inverseperm(perm,n) P_Elem perm; /* pointe sur la permutation sur [n] */ Elem n; /* dimension de la permutation */ { P_Elem perminv; /* pointe sur la permutation inverse */ Elem i; /* indice de la permutation */ TESTCALLOC(perminv,n,Elem); perminv--; for (i = 1; i <= n; i++) perminv[perm[i]] = i; return(perminv); } /*===========================================================================*/ /* editions */ /*===========================================================================*/ /*****************************************************************************/ /* edition des arbres des involutions/permutations a motifs exclus */ /*****************************************************************************/ Void edit() { IndDescrip idomaine; /* indice des domaines */ for (idomaine = 0; idomaine < DIMDOMAINES; idomaine++) if (domaines[idomaine].dde) { if (echo) printf("\t%s\n",domaines[idomaine].txt); edit1dom(idomaine); } } /*****************************************************************************/ /* edition d'un domaine selon le format de sortie demande */ /*****************************************************************************/ Void edit1dom(idomaine) IndDescrip idomaine; /* indice des domaines */ { Void editascii(); /* fonction d'edition en ASCII */ Void edityam(); /* fonction d'edition des couples de mots de Yamanushi */ Void editparenth(); /* fonction d'edition pour les parentheses */ #ifdef OS_UNIX Void editcabri(); /* fonction d'edition CABRI */ #endif Void edit2nbfils(); /* fonction d'edition de 2 fois nombres de fils */ Void editregle(); /* fct d'edition des nombres de fils pour ts successeurs */ Void editstats(); /* fonction d'edition de toutes les statistiques */ IndDescrip isortreel; /* indice des sorties reelles */ for (isortreel = 0; isortreel < DIMSORTREEL; isortreel++) if (sortuser[sortreel[isortreel].refuser].dde) switch (sortuser[sortreel[isortreel].refuser].type) { case TYPESORTIEPRCS : if (isortreel != I_SORTREEL_CABRI) FOPEN(fout,sortuser[sortreel [isortreel].refuser].nomf); switch (isortreel) { case I_SORTREEL_ARBREASCII : prcsforet(idomaine,editascii); break; case I_SORTREEL_YAM : prcsforet(idomaine,edityam); break; case I_SORTREEL_ARBREPARENTH : prcsforet(idomaine,editparenth); break; case I_SORTREEL_CABRI : #ifdef OS_UNIX prcsforet(idomaine,editcabri); #endif break; case I_SORTREEL_2NBFILS : prcsforet(idomaine,edit2nbfils); break; case I_SORTREEL_REGLE : prcsforet(idomaine,editregle); break; case I_SORTREEL_TTESSTATS : prcsforet(idomaine,editstats); break; default : erreur(23); break; } if (isortreel != I_SORTREEL_CABRI) FCLOSE(fout); break; case TYPESORTIETABL : prcstable(idomaine,isortreel); break; case TYPESORTIEGDTABL : printf("nouvelles sorties non encore implementees\n"); break; default : erreur(23); break; } } /*****************************************************************************/ /* parcours de la foret pour une fonction d'edition */ /*****************************************************************************/ Void prcsforet(idomaine,fctedit) IndDescrip idomaine; /* indice des domaines */ Void (* fctedit)(); /* fonction d'edition */ { P_Racine rac; /* racine de l'arbre a editer */ for (rac = domaines[idomaine].foret; rac != NULL; rac = rac->suiv) if (rac->ptr_permtete != NULL) (* fctedit)(rac,rac->ptr_permtete); } /*---------------------------------------------------------------------------*/ /* edition des permutations au format d'un arbre ASCII */ /*---------------------------------------------------------------------------*/ /*****************************************************************************/ /* edition des permutations au format d'un arbre ASCII */ /*****************************************************************************/ Void editascii(rac,p) P_Racine rac; /* racine de l'arbre a editer */ P_Sommet p; /* permutation a editer */ { Booleen finligne; /* indique le dernier caractere affiche */ finligne = VRAI; edascii(rac,p,&finligne); } /*****************************************************************************/ /* edition recursive des permutations au format d'un arbre ASCII */ /*****************************************************************************/ Void edascii(rac,pere,p_finligne) P_Racine rac; /* racine de l'arbre a editer */ P_Sommet pere; /* permutation a editer */ P_Booleen p_finligne; /* indique le dernier caractere affiche */ { if (pere != NULL) { P_Sommet fils; /* permutation suivante (fils) a editer */ affascii(rac,pere,p_finligne); for (fils = pere->filsaine; fils != NULL; fils = fils->suiv) edascii(rac,fils,p_finligne); } } /*****************************************************************************/ /* affichage d'une permutation au format d'un arbre ASCII */ /*****************************************************************************/ Void affascii(rac,p,p_finligne) P_Racine rac; /* racine de l'arbre a editer */ P_Sommet p; /* permutation a afficher */ P_Booleen p_finligne; /* indique le dernier caractere affiche */ { Elem i; /* indice de la permutation a afficher */ /* afficher des permutations "blanches" */ if (*p_finligne) { Elem n; /* permutations precedentes (blanches) a afficher */ for (n = rac->n_tete; n < p->n; n++) { Int nbblancs; /* nombre de caracteres blancs a afficher */ /* chaque chiffre occupe un caractere */ nbblancs = (n < 10) ? (2 * n + 1) : (3 * n - 8); nbblancs += (n < 9) ? 3 : 4; fprintf(fout,"%*s",nbblancs,""); fprintf(fout,"%s",STRTABPERM); } } /* affiche la permutation */ for (i = 1; i <= p->n + 1; i++) { fprintf(fout,"%c", tstbool8(p->sitesactifs,i) ? SITEACTIF : SITEINACTIF); if (i <= p->n) fprintf(fout,"%u",p->perm[i]); } fprintf(fout,"(%u)",p->nbfils); if (p->n >= 9 && p->nbfils <= 9) fprintf(fout," "); *p_finligne = (p->filsaine == NULL); fprintf(fout,"%s",*p_finligne ? STRNLPERM : STRTABPERM); } /*---------------------------------------------------------------------------*/ /* edition des permutations et couples mots Yamanushi (Robinson-Schensted) */ /*---------------------------------------------------------------------------*/ /*****************************************************************************/ /* edition des permutations et des couples de mots de Yamanushi */ /*****************************************************************************/ Void edityam(rac,p) P_Racine rac; /* racine de l'arbre a editer */ P_Sommet p; /* permutation a editer */ { edyam(rac,p); } /*****************************************************************************/ /* edition recursive des permutations et des couples de mots de Yamanushi */ /*****************************************************************************/ Void edyam(rac,pere) P_Racine rac; /* racine de l'arbre a editer */ P_Sommet pere; /* permutation a editer */ { if (pere != NULL) { P_Sommet fils; /* permutation suivante (fils) a editer */ affyam(pere); for (fils = pere->filsaine; fils != NULL; fils = fils->suiv) edyam(rac,fils); } } /*****************************************************************************/ /* affichage d'une permutation et du couple de mots de Yamanushi (R-S) */ /*****************************************************************************/ Void affyam(p) P_Sommet p; /* permutation a afficher */ { Elem i; /* indice de la permutation a afficher et de part[] */ Elem part[DIM_NMAX_YAM+1]; /* parts */ Elem tabt[DIM_NMAX_YAM][DIM_NMAX_YAM]; /* table T */ Elem tabu[DIM_NMAX_YAM][DIM_NMAX_YAM]; /* table U */ /* affiche la permutation */ for (i = 1; i <= p->n; i++) { fprintf(fout,"%u",p->perm[i]); if (i < p->n) fprintf(fout,"%c",STRSEPARELEM); } /* calcul des 2 tableaux (Robinson-Schensted) T,U associes a la permutation */ for (i = 1; i <= DIM_NMAX_YAM; i++) part[i] = 0; for (i = 1; i <= p->n; i++) { Elem e; /* element successivement insere */ Elem l; /* ligne ou l'element doit s'inserer */ e = p->perm[i]; l = 1; while (part[l] > 0 && e < tabt[l][part[l]]) { Elem j; /* indice du + petit des + grands en j(eme) colonne */ Elem svg; /* pour echanger e et tabt[l][j] */ for (j = 1; tabt[l][j] < e; j++) ; svg = e; e = tabt[l][j]; tabt[l][j] = svg; l++; } (part[l]) ++; tabt[l][part[l]] = e; tabu[l][part[l]] = i; } /* affiche le couple de mots de Yamanushi associe aux 2 tableaux */ aff1yam(tabt,part,p->n); aff1yam(tabu,part,p->n); /* fin de ligne */ fprintf(fout,"\n"); } /*****************************************************************************/ /* affichage d'une permutation et du couple de mots de Yamanushi (R-S) */ /*****************************************************************************/ Void aff1yam(pp_tab,p_part,n) P_Elem pp_tab; /* pointeur sur l'un des tableaux associe a la permutation */ P_Elem p_part; /* pointeur sur les parts */ Elem n; /* dimension de la permutation */ { Char yam[DIM_NMAX_YAM+1]; /* mot de yamanushi du tableau */ Elem l; /* indice de part */ yam[n+1] = '\0'; for (l = 1; p_part[l]; l++) { Elem j; /* deuxieme indice du tableau */ for (j = 1; j <= p_part[l]; j++) yam[pp_tab[l*DIM_NMAX_YAM+j]] = elemtoc(l); } fprintf(fout,"\t%*s",n,yam+1); } /*---------------------------------------------------------------------------*/ /* edition des permutations au format d'un arbre parenthese */ /*---------------------------------------------------------------------------*/ /*****************************************************************************/ /* edition des permutations au format d'un arbre parenthese */ /*****************************************************************************/ Void editparenth(rac,p) P_Racine rac; /* racine de l'arbre a editer */ /* INUTILISE */ P_Sommet p; /* permutation a editer */ { P_Char mot; /* mot final (de la racine) des parentheses */ /* |mot| <= (nmax + 1)! + 2 * Somme(n=1..nmax) n! + '\0' */ /* ex.: |mot|<=4,12,42,186 pour nmax::=+1,+2,+3,+4 */ mot = edparenth(p); affmotparenth(mot); CFREE(mot); } /*****************************************************************************/ /* edition recursive des permutations au format d'un arbre parenthese */ /*****************************************************************************/ P_Char edparenth(pere) P_Sommet pere; /* permutation a afficher */ { P_Char s; /* pointe sur la chaine contenant le mot de parentheses */ if (pere->filsaine == NULL) { TESTCALLOC(s,2,Char); s[0] = elemtoc(pere->nbfils); s[1] = '\0'; } else { Short lgs; /* longueur de s */ P_Sommet fils; /* permutation suivante (fils) a editer */ PP_Char tabs; /* table des pointeurs sur les chaines des fils */ Elem itabs; /* indice de tabs[] */ /* allocation de tabs[] */ TESTCALLOC(tabs,pere->nbfils,P_Char); tabs--; /* insertion des mots de parentheses des fils en ordre */ lgs = 3; /* pour '(', ')', '\0' */ itabs = 0; for (fils = pere->filsaine; fils != NULL; fils = fils->suiv) { P_Char tmps; /* pointe temporairement le mot du fils */ Elem jtabs; /* indice de tabs[] */ Booleen fini; /* force l'arret de la boucle */ tmps = edparenth(fils); jtabs = itabs; fini = FAUX; while (jtabs >= 1 && ! fini) if (cmpparenth(tmps,tabs[jtabs])) { tabs[jtabs+1] = tabs[jtabs]; jtabs--; } else fini = VRAI; tabs[jtabs+1] = tmps; lgs += strlen(tmps); itabs++; } TESTCALLOC(s,lgs,Char); /* creation du mot de parentheses en concatenant ceux des fils */ strcpy(s,"("); for (itabs = 1; itabs <= pere->nbfils; itabs++) { strcat(s,tabs[itabs]); CFREE(tabs[itabs]); } strcat(s,")"); /* liberation de tabs[] */ CFREE(tabs+1); } return(s); } /*****************************************************************************/ /* compare deux mots de parentheses */ /*****************************************************************************/ Booleen cmpparenth(s1,s2) /* retourne VRAI si s2 strictement + grand que s1 */ P_Char s1; /* 1ere chaine a comparer */ P_Char s2; /* 2eme chaine a comparer */ { /* detection de l'egalite */ while (*s1 == *s2) { if (*s1 == '\0') return(FAUX); s1++; s2++; } /* en cas d'inegalite */ /* priorites en ordre croissant : )0123456789( <--> x29,x30..x39,x28 */ if (*s1 == '(' || *s2 == '(') return(*s2 == '('); else return(*s2 > *s1); } /*****************************************************************************/ /* affichage du mot de parentheses de l'arbre */ /*****************************************************************************/ Void affmotparenth(s) P_Char s; /* pointe sur le mot de parentheses a ecrire */ { Short istr; /* indice de la portion de s consideree */ istr = 0; while (*s) { if (istr == NBCARPARENTH) { fprintf(fout,"\n"); istr = 0; } fprintf(fout,"%c",*s); istr++; s++; } fprintf(fout,"\n"); } /*---------------------------------------------------------------------------*/ /* edition des permutations au format CABRI */ /*---------------------------------------------------------------------------*/ #ifdef OS_UNIX /*****************************************************************************/ /* edition des permutations au format CABRI */ /*****************************************************************************/ Void editcabri(rac,p) P_Racine rac; /* racine de l'arbre a editer */ P_Sommet p; /* permutation a editer */ /* INUTILISE */ { P_Coordcabri tabcoord; /* table des resultats */ struct ParamCabri prmcabri; /* parametres d'edition CABRI */ Elem n; /* nombre d'element d'une permutation sur [n] */ Resultat numero; /* numero courant de la permutation affichee */ Resultat numdern; /* numero de derniere permutation affichee */ /* INUTILISE */ Indcoordcabri orddern; /* derniere ordonnee */ P_FILE ftmp; /* fichier temporaire en sortie pour CABRI */ /* debut et edition de l'entete CABRI */ FOPEN(fout,NOMFCABRI); if ((ftmp = fopen(NOMFTMPCABRI,"w")) == NULL) erreur(11); afftetecabri(rac->nbperm); /* initialisation des parametres d'edition CABRI */ if (rac->nmax < rac->n_tete + NMAX) { prmcabri.mrgabs = MRGABS4; prmcabri.mrgord = MRGORD4; prmcabri.offabs = OFFABS4; prmcabri.offord = OFFORD4; prmcabri.szshap = SZSHAP4; prmcabri.szfont = SZFONT4; } else { prmcabri.mrgabs = MRGABS5; prmcabri.mrgord = MRGORD5; prmcabri.offabs = OFFABS5; prmcabri.offord = OFFORD5; prmcabri.szshap = SZSHAP5; prmcabri.szfont = SZFONT5; } /* initialisation de tabcoord[] */ TESTCALLOC(tabcoord,rac->nmax - rac->n_tete + 1,struct Coordcabri); tabcoord--; for (n = rac->n_tete; n <= rac->nmax; n++) { tabcoord[n].abs = prmcabri.mrgabs + prmcabri.offabs * (n - rac->ptr_permtete->n); tabcoord[n].ord = prmcabri.mrgord - prmcabri.offord; } /* numerotation et edition */ numero = PREMNUMCABRI; numdern = numcabri(rac,ftmp,rac->ptr_permtete,PREMNUMCABRI,&numero,tabcoord, &prmcabri,&orddern); /* fin */ CFREE(tabcoord+1); fclose(ftmp); FCLOSE(fout); fusioncabri(); } /*****************************************************************************/ /* affichage de l'entete du format CABRI */ /*****************************************************************************/ Void afftetecabri(nbperm) Resultat nbperm; /* nombre total de permutations */ { fprintf(fout,"CABRI Version 3.0, june 1990%c",CRCABRI); fprintf(fout,"alpha_num grid : -20%c",CRCABRI); fprintf(fout,"selection: %.0f%c",PREMNUMCABRI,CRCABRI); /* fprintf(fout,"selection of edges: %c",CRCABRI); */ fprintf(fout,"#vertices: %.0f ",nbperm); fprintf(fout,"#edges: %.0f%c",(nbperm == 0.0) ? 0.0 : (nbperm - 1),CRCABRI); fprintf(fout,"%c",CRCABRI); } /*****************************************************************************/ /* numerote en CABRI recursivement les sommets de l'arbre des permutations */ /*****************************************************************************/ Resultat numcabri(rac,ftmp,pere,numpere,p_numero,tabcoord,p_prmcabri,p_ordpere) /* de +, la fonction choisit l'ordonnee : . la moyenne des ordonnees des 2 fils extremes (1er et dernier) pour un sommet . le Max des ordonnees + OFFORD pour une feuille */ P_Racine rac; /* racine de l'arbre a editer */ P_FILE ftmp; /* fichier temporaire en sortie pour CABRI */ P_Sommet pere; /* pointe sur la permutation pere */ Resultat numpere; /* numero du pere */ P_Resultat p_numero; /* pointe sur numero courant de la permutation affichee */ P_Coordcabri tabcoord; /* table des resultats */ P_ParamCabri p_prmcabri; /* pointe sur les parametres d'edition CABRI */ P_Indcoordcabri p_ordpere; /* pointe sur l'ordonnee pere a renseigner */ { Resultat num; /* numero affecte a la permutation courante */ num = *p_numero; (*p_numero)++; if (pere->filsaine != NULL) { P_Sommet fils; /* pointe successivement sur les fils */ P_Resultat tabnumfils; /* table des numeros des fils */ Elem i; /* indice de tabnumfils */ Indcoordcabri ord1erfils; /* ordonnee du premier fils */ Indcoordcabri ordfils; /* ordonnee du fils */ TESTCALLOC(tabnumfils,pere->nbfils,Resultat); i = 0; for (fils = pere->filsaine; fils != NULL; fils = fils->suiv) { tabnumfils[i] = numcabri(rac,ftmp,fils,num,p_numero,tabcoord, p_prmcabri,ªils); if (i == 0) ord1erfils = ordfils; i++; } *p_ordpere = (ord1erfils + ordfils) / 2; affpermcabri(ftmp,pere,numpere,num,tabnumfils,tabcoord,p_prmcabri, *p_ordpere); CFREE(tabnumfils); } else { Elem n; /* indice de tabcoord */ *p_ordpere = tabcoord[rac->nmax].ord; for (n = rac->nmax - 1; n >= rac->n_tete; n--) if (tabcoord[n].ord > *p_ordpere) *p_ordpere = tabcoord[n].ord; *p_ordpere += p_prmcabri->offord; affpermcabri(ftmp,pere,numpere,num,NULL,tabcoord,p_prmcabri, *p_ordpere); } return(num); } /*****************************************************************************/ /* affiche en CABRI une permutation */ /*****************************************************************************/ Void affpermcabri(ftmp,p,numpere,num,tabnumfils,tabcoord,p_prmcabri,ord) /* Rmq. : les \n sont ici remplaces par des \t car ils sont retraites par fusioncabri() */ P_FILE ftmp; /* fichier temporaire en sortie pour CABRI */ P_Sommet p; /* pointe sur la permutation */ Resultat numpere; /* numero de la permutation pere */ Resultat num; /* numero de la permutation courante */ P_Resultat tabnumfils; /* table des numeros des fils */ P_Coordcabri tabcoord; /* table des resultats */ P_ParamCabri p_prmcabri; /* pointe sur les parametres d'edition CABRI */ Indcoordcabri ord; /* ordonnee de la permutation a afficher */ { Elem i; /* indice de tabnumfils */ Short degre; /* degre de la permutation */ /* 1ere ligne : degre: */ degre = (tabnumfils == NULL) ? 0 : p->nbfils; if (numpere != num) degre++; fprintf(ftmp,"%.0f degree: %d ",num,degre); if (numpere != num) fprintf(ftmp,"%.0f ",numpere); if (tabnumfils != NULL) for (i = 0; i < p->nbfils; i++) fprintf(ftmp,"%.0f ",tabnumfils[i]); fprintf(ftmp,"\t"); /* 2eme ligne : coord.: val.: shape: size: offsets: */ fprintf(ftmp,"\tcoord.: %ld %ld",tabcoord[p->n].abs,ord); tabcoord[p->n].ord = ord; fprintf(ftmp," val.: %d ",p->nbfils); fprintf(ftmp,"shape: round size: %d offsets: 7 4\t",p_prmcabri->szshap); /* 3eme ligne : label: font: size: face: