Fonctions sur les ensembles revisitées...
par Michel J Dumontier
Des fonctions utiles sur les
ensembles :
Les fonctions que l’on trouve généralement dans la littérature, ne correspondent pas toujours à ce que l’on attend d’elles, ou ne sont pas toujours exactes.
Ainsi on est parfois amené à les réécrire pour son propre usage et pour des applications concrètes.
C’est en lisant l’article de Joseph de Kerf dans le n° 22 des ‘Nouvelles d’APL’, que j’ai eu l’idée de présenter quelques fonctions sur les ensembles que j’ai dû réécrire.
Nous écrirons des fonctions qui s’appliquent essentiellement à des vecteurs homogènes.
Liste des fonction étudiées : intersection, contenance, sauf (=sans ou complément), union, unique (=nub), différence, égale, identique. (sans oublier l’appartenance qui est une fonction ensembliste mais primitive d’APL)
Conventions:
n Nous suffixerons les noms des fonctions que l’on trouve généralement dans la littérature par la lettre G comme dans INTERG.
n Nous suffixerons les noms des fonctions de Joseph de Kerf par DK comme dans INTERDK.
n Nous suffixerons les noms des fonctions que j’ai dû réécrire par D comme dans INTERD (car INTERG ne suffit pas).
n Les fonctions non suffixées sont aussi des fonctions que j’ai dû écrire, mais je ne sais pas si elles existent déjà dans la littérature (probablement souvent): c’est connu que chacun réécrit ce qui existe déjà sans le savoir!
Remarque: On s’attend à ce que certaines fonctions (exemples: réunion, intersection) soient symétriques (pour A et B étant deux ensembles A inter B doit être égal à B inter A). Un ensemble est une collection d’objets, il n’y a pas forcément une relation d’ordre possible, et l’ensemble (A,B,C) est égal à l’ensemble (B,A,C).
D’autre part,
en APL, l’argument gauche a un rôle particulier (déterminant).
Exemple : pour la fonction d’appartenance, la forme du résultat a la forme de l’argument gauche :
Appartenance: (fonction primitive d’APL)
2¹3 4 5
0
2 3¹ 3 4 5
0 1
1±X Fonction sinus
2±X Fonction cosinus
2!7 Fonction Combinaisons
21
2.5!5.5 Fonction Béta complète
14.4375
Intersection:
Donnons la
fonction d'intersection exacte:
ZL INTERDK R
[1] Z((Z¼Z)=¼½Z)/Z(L,L),R,R
[2] Z((+/Z°.=L)+/Z°.=R)/Z
'CHIQUE' INTERDK 'NICHE'
CHIE
'NICHE' INTERDK 'CHIQUE'
ICHE
Les éléments du résultat sont dans le même ordre que celui de l’argument gauche.
Voici une
autre version qui se comporte de la même manière:
ZA INTERD B;BB;I;IO;R
[1] IO0
ª Z0A
[2]
BO:IB¼R1A ª
(I=½B)/INC
ª BB(½B)½1 ª BB[I]0 ª BBB/B ª ZZ,R
[3] INC:A1A ª
(0¬½A)/BO
Donnons ici la
fonction d’intersection que l’on trouve généralement:
ZX INTERG Y
[1] Z(X¹Y)/X
Voyons son
comportement vis à vis d’une fonction qui donne l’intersection stricte:
'AMSTRAMGRAM' INTERD 'RAMSES'
AMSR
'AMSTRAMSGRAMMES' INTERD 'RAMSES'
AMSSRE
Il y a trois S
à gauche, deux à droite: l’intersection est bien deux S.
'AMSTRAMGRAM' INTERG 'RAMSES'
AMSRAMRAM
Bien que ce ne soit pas une intersection stricte, la version INTERG peut servir si on veut conserver dans l’argument gauche tous les éléments appartenant à l’argument droit.
Contenance:
Voici ce qu’on
trouve généralement pour la contenance, avec le test qui suit:
ZX CONTIENTG Y
[1] Z^/Y¹X
'NICHE' CONTIENTG 'CHIEN'
1
'NICHE' CONTIENTG 'CHIENNE'
1
Bien que la deuxième proposition paraisse juste dans la réalité, elle est fausse, à moins de considérer les éléments de l’argument gauche comme génériques: en fait, il manque un N et un E dans l’argument gauche pour former ‘CHIENNE’.
Réécrite, la
fonction suivante fonctionne plus correctement (en s’inspirant de la fonction
DIFFERENCE de Joseph de Kerf):
ZL CONTIENTD R;D
[1] Z((Z¼Z)=¼½Z)/Z(L,L),R,R
[2] Z((×D)×D(+/Z°.=L)-+/Z°.=R)/Z
[3] Z~0¹D0
'NICHE' CONTIENTD 'CHIENNE'
0
'CHIENNE' CONTIENTD 'NICHE'
1
(Cette fois-ci, la deuxième proposition ne paraît pas possible dans la réalité, alors que le résultat est vrai!)
Sauf: (peut s’appeler aussi sans, complément)
Prenons par exemple la version SANS de l’article cité plus haut et baptisons-la SAUFG, car c’est ainsi qu’on la trouve généralement.
Voici la
fonction avec un exemple:
ZA SAUFG B
[1] Z(~A¹B)/A,A
'RUSSIA' SAUFG 'U.S.S.R.'
IA
On ne tient pas compte dans cette version des éléments (comme ici le point) qui existent dans l’argument droit et pas dans l’argument gauche.
Par contre,
SAUFG peut servir comme dans l’exemple suivant :
'U.S.A.' SAUFG '.,-'
USA
Union:
La version générale (imparfaite) utilise la fonction ensembliste courante SAUFG.
Voici la
fonction UNIONG et un exemple:
ZA UNIONG B
[1] ZA,B
SAUFG A
3 2 1 UNIONG 2 3 4 2
3 2 1 4
Ce n’est pas une UNION au sens ensembliste (il manque une fois l’élément 2 dans le résultat).
Donnons
maintenant les deux fonctions correctes UNIONDK et UNIOND avec le même exemple:
ZL UNIONDK R
[1] Z((Z¼Z)=¼½Z)/Z(L,L),R,R
[2] Z((+/Z°.=L)+/Z°.=R)/Z
ZB UNIOND A;C;I;J;IO
[1] IO0
ª I0 ª A,A ª ZB,B ª
(0=½A)/FIN
[2] BO:JB¼A[I]
ª
(J=½B)/INC ª C(½B)½1 ª C[J]0 ª BC/B ª A(IA),(I+1)A
ª
II-1
[3] INC:
((½A)=II+1)/FIN
ª
((0¬½B)^0¬½A)/BO
[4] FIN:ZZ,A
3 2 1 UNIONDK 2 3 4 2
3 2 2 1 4
3 2 1 UNIOND 2 3 4 2
3 2 1 4 2
Elles fonctionnent différemment mais elles donnent chacune le même résultat, juste (à une permutation près des éléments, mais ce sont les mêmes bons éléments: dans la version DK, les éléments identiques sont rassemblés; dans la version D, les éléments apparaissent dans l’ordre où on les rencontre dans l’argument gauche puis dans l’argument droit).
Pour reprendre
un exemple donné dans ce même article:
'ABRACADABRA' UNIONDK 'YABADABADOE'
AAAAABBRRCDDYOE
'ABRACADABRA' UNIOND 'YABADABADOE'
ABRACADABRAYDOE
Unique:
Ce n’est pas à proprement parler une fonction ensembliste qu’on pourrait baptiser réduction d’un ensemble, mais c’est une fonction auxiliaire très commode que l’on trouve souvent dans la littérature sous le nom de NUB (noyau); on la trouve même sous forme de fonction primitive en J appelée ESSENTIEL. Il y a même mieux en J: sa compagne la fonction CRIBLE DE L’ESSENTIEL, très utile.
Voici NUB avec
un exemple sans commentaire, cela va de soi:
ZNUB X
[1] Z((¼½X)=X¼X)/X
NUB 'SUISSESSES'
SUIE
Différence:
Rappelons la
fonction DIFFERENCEDK sur laquelle il n’y a rien à dire et donnons un exemple:
ZL DIFFERENCEDK R;D
[1] Z((Z¼Z)=¼½Z)/Z(L,L),R,R
[2] Z((D>0)×D(+/Z°.=L)-+/Z°.=R)/Z
'ABRACADABRA' DIFFERENCEDK 'ARCHEDENOE'
AAAABBR
Voici une
fonction qui tient compte des éléments de l’argument gauche et qui donne une
valeur réelle de la différence entre les éléments de l’argument gauche et ceux
de l’argument droit.
ZL DIFFENSD R;D
[1] Z((Z¼Z)=¼½Z)/Z(L,L),R,R
[2] Z((×D)×D(+/Z°.=L)-+/Z°.=R)/Z
[3] (D¬0)/D
'ABRACADABRA'
DIFFENSD 'ARCHEDENOE'
4 2 1 ¯1 ¯3 ¯1 ¯1
AAAABBRHEEENO
Et voici une
dernière version qui utilise la fonction NUB et qui donne au dessus du résultat
qui ne comporte qu’une seule occurrence de chaque élément, la valeur de la
différence (autant d’éléments que de valeurs de pondération):
ZL DIFFENSND R;D
[1] Z((Z¼Z)=¼½Z)/Z(L,L),R,R
[2] ZNUB
((×D)×D(+/Z°.=L)-+/Z°.=R)/Z
[3] (D¬0)/D
'ABRACADABRA' DIFFENSND 'ARCHEDENOE'
4 2 1 ¯1 ¯3 ¯1 ¯1
ABRHENO
Interprétation: il y a 4 éléments ‘A’ en excédant dans l’argument gauche par rapport à l’argument droit, 2 éléments ‘B’ etc... un ‘H’ manquant, 3 ‘E’ manquant etc.. il y a autant de D, ils se compensent et disparaissent dans la différence! ce qui est normal.
Égale:
On peut aussi avoir besoin de savoir si deux objets sont strictement égaux:
Voici sa
définition ainsi que deux exemples pour illustrer son utilisation:
ZA EGALE B;D;E
[1] D½A
ª E½B ª
(D=E)/SUI ª Z0 ª
0
[2] SUI:Z^/A=B
[3]
F'CHAT'
E'CAT'
F EGALE 'CHAT'
1
E EGALE 'CHAT'
0
Identique:
Nous dirons que deux ensembles sont identiques s’ils sont composés des mêmes éléments quel que soit le nombre d’occurrences de chaque élément dans chaque ensemble.
Voici la
fonction ainsi que deux exemples pour illustrer son utilisation:
ZA IDENTIQUE B
[1] Z^/(A¹B),B¹A
'ISO.' IDENTIQUE 'O.S.I.'
1
ETHANAMIDE'CHHH-CO-NHH'
'CHON-' IDENTIQUE ETHANAMIDE
1
La fonction étant
symétrique, on peut l’utiliser également comme suit :
ETHANAMIDE IDENTIQUE 'CHON-'
1