Monoide.py 9.42 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
from Morphisme import Morphisme
from CategorieLibre import CategorieLibre
from GrapheDeComposition import MGC,GC, GrapheDeComposition
from CategorieProduit import CategorieProduit
import random
from config import *
import itertools

class ElementMonoide(Morphisme):
    """Un élément de monoïde est une flèche de l'unique objet (1) de la catégorie vers lui-même."""
    def __init__(self, nom:str = None, is_identite:bool = False):
        Morphisme.__init__(self,1,1,nom,is_identite)
        
    def verifier_coherence(self):
        if not (self.source == self.cible == 1):
            raise Exception("ElementMonoide n'a pas pour cible ou pour source 1."+repr(self))

class Monoide(CategorieLibre):
    """Un `Monoide` est une catégorie à un seul objet.
    Les flèches de la catégorie représentent les éléments du monoïde, l'identité l'élément neutre.
    La loi de composition de la catégorie représente la loi de composition interne.
    
    Les classes filles doivent implémenter les méthodes :
        - identite(self,objet:any = None) -> Morphisme: renvoie l'element neutre peu import l'objet
        - elements(self) -> set : renvoie l'ensemble des éléments du Monoïde où chaque élément est un ElementMonoide.
        ces deux méthodes définissent le graphe sous-jacent avec les objets de la catégorie"""
    
    def __init__(self, nom:str = "Monoide"):
        CategorieLibre.__init__(self,{1},nom)
        
    def __ior__(self, objets:any):
        if objets == {1}:
            CategorieLibre.__ior__(self,{1})
            return self
        raise Exception("Tentative d'ajout d'un objet à un monoide : "+str(objets))
        
    def __isub__(self, objets:any):
        raise Exception("Tentative de retirer un objet à un monoide : "+str(objets))
    
    def existe_morphisme(self, source:any, cible:any) -> bool:
        return source == cible == 1
        
    def identite(self) -> ElementMonoide:
        raise NotImplementedError("Les classes filles doivent implementer cette methode qui renvoie l'element neutre.")
        
    def elements(self) -> set:
        raise NotImplementedError("Les classes filles doivent implementer cette methode qui renvoie les elements du monoide.")
        
   
class ElementMonoideGC(ElementMonoide,MGC):
    """Un élément de monoïde graphe de composition est un élément de monoïde instanciable utilisé pour le monoïde
    graphe de composition."""
    def __init__(self,nom:str = None,is_identite:bool = False):
        ElementMonoide.__init__(self,nom,is_identite)
        MGC.__init__(self,1,1,nom,is_identite)
        
    def verifier_coherence(self):
        ElementMonoide.verifier_coherence(self)
        MGC.verifier_coherence(self)
   
class MonoideGC(GrapheDeComposition,Monoide):
    """Un monoïde graphe de composition est un monoïde instanciable.
    C'est un graphe de composition à un objet."""
    
    def __init__(self,nom:str = "MonoïdeGC"):
        GrapheDeComposition.__init__(self,{1},nom)
        Monoide.__init__(self,nom)
    
    def identite(self, objet:any = None) -> ElementMonoideGC:
        return GrapheDeComposition.identite(self,1)
    
    def elements(self) -> set:
        return GrapheDeComposition.__call__(self,{1},{1})
        
    def __ior__(self, elements:set) -> 'MonoideGC':
        for elem in elements:
            if elem == 1:
                GrapheDeComposition.__ior__(self,{1})
                return self
            if not issubclass(type(elem),ElementMonoideGC):
                raise Exception("Tentative d'ajouter un element de monoide de type inconnu "+str(elem))
            GrapheDeComposition.__ior__(self,{elem})
        return self
            
    def __isub__(self, elements:set) -> 'MonoideGC':
        for elem in elements:
            if not issubclass(type(elem),ElementMonoideGC):
                raise Exception("Tentative de suppression d'un element de monoide de type inconnu "+str(elem))
            GrapheDeComposition.__isub__(self,{elem})
        return self

class PetitMonoideAleatoire(MonoideGC):
    """Monoïde fini dont la table de loi de composition interne est choisie aléatoirement.
    Les éléments du monoïde seront des flèches nommées par des nombres allant de 1 
    jusqu'au nombre d'éléments moins un sauf l'indentité qui représente l'élément neutre.
    La taille maximale de ce monoïde est 5, sinon le temps de calcul est trop grand.
    Pour un monoïde aléatoire plus grand, utiliser un `MonoideAleatoire` qui sera un produit de `PetitMonoideAleatoire`."""
    
    def __init__(self, nb_elements:int = random.randint(1,5), nom:str = "Petit monoïde aléatoire"):
        """`nb_elements` est le nombre d'éléments du monoïde, si `nb_elements` = 1, alors il n'y a que l'identité dans le monoïde.
        `nb_elements` doit être inférieur à 5, sinon le temps de calcul est trop long.
        Pour un monoïde plus grand, utiliser `MonoideAleatoire`."""
        if DEBUG_MONOIDE_ALEATOIRE:
            print("Début de création d'un monoïde à "+str(nb_elements)+" éléments")
        if nb_elements > 5:
            raise Exception("Le nombre d'elements d'un PetitMonoideAleatoire doit etre inferieur ou egal a 5.")
        elements = list(range(nb_elements)) #le 0 va représenter l'identité 
        associativite_verifiee = False
        while not associativite_verifiee:
            table = dict()
            associativite_verifiee = True
            for a,b in itertools.product(elements,repeat=2):
                if (a,b) not in table:
                    table[(a,b)] = random.choice(elements) if a*b != 0 else a+b
                    # si a ou b est 0 (le produit est 0) alors on renvoie l'autre element (a+b vaut l'autre element puisque 0 est neutre par l'addition)
            
                    # on force l'associativité si on peut
                    for c in elements:
                        if (table[(a,b)],c) in table and (b,c) in table:
                            if (a,table[(b,c)]) not in table:
                                table[(a,table[(b,c)])] = table[(table[(a,b)],c)]
                            elif table[(table[(a,b)],c)] != table[(a,table[(b,c)])]:
                                associativite_verifiee = False
                                table[(a,table[(b,c)])] = table[(table[(a,b)],c)]
                                break
                    else:
                        continue
                    break
            if not associativite_verifiee:
                continue
                     
            #on a une table aléatoire
            #maintenant on vérifie l'associativité
            associativite_verifiee = False 
            for a,b,c in itertools.product(elements,repeat=3):
                if table[(table[(a,b)],c)] != table[(a,table[(b,c)])]:
                    break
            else:
                associativite_verifiee = True
        # on a notre table de composition
        MonoideGC.__init__(self,nom)
        fleches = {i:ElementMonoideGC(str(i)) for i in range(1,nb_elements)}
        fleches[0] = self.identite()
        self |= {fleches[i] for i in range(1,nb_elements)}
        for a,b in itertools.product(elements,repeat=2):
            if fleches[a]@fleches[b] != fleches[table[(a,b)]]:
                MGC.identifier_morphismes(fleches[a]@fleches[b],fleches[table[(a,b)]])
        if DEBUG_MONOIDE_ALEATOIRE:
            print("Fin de création d'un monoïde à "+str(nb_elements)+" éléments")

def facteurs_premiers(n):
    while n > 1:
        for i in range(2, int(n**0.5)+1):
            if not n % i:
                n //= i
                yield i
                break
        else:
            yield n
            break

class MonoideAleatoire(Monoide):
    """Monoïde dont la table de loi de composition interne est tirée aléatoirement.
    Si le nombre d'éléments du monoïde est supérieur à 5, on créé un produit de `PetitMonoideAleatoire`.
    Si le (grand) nombre d'éléments est premier ou peu décomposable, on se réserve le droit de changer
    le nombre d'élément pour qu'il soit factorisable en facteurs inferieurs ou égaux à 5."""
    def __init__(self, nb_elements:int = random.randint(1,20), nom:str = "Monoïde aléatoire"):
        if DEBUG_MONOIDE_ALEATOIRE:
            print("Début de création d'un monoïde à "+str(nb_elements)+" éléments")
        while max(facteurs_premiers(nb_elements)) > 5:
            nb_elements -= 1
        if DEBUG_MONOIDE_ALEATOIRE:
            print("Simplification du nombre d'éléments à "+str(nb_elements))
        petits_monoides = [PetitMonoideAleatoire(x) for x in facteurs_premiers(nb_elements)]
        Monoide.__init__(self,nom)
        self.__produit = CategorieProduit(*petits_monoides)
        if DEBUG_MONOIDE_ALEATOIRE:
            print("Fin de création d'un monoïde à "+str(nb_elements)+" éléments")
        
    def identite(self, objet:any) -> Morphisme:
        print(objet)
        return self.__produit.identite(tuple(objet for i in range(len(self.__produit))))
        
    def __call__(self, sources:set, cibles:set) -> set:
        return self.__produit({tuple(source for i in range(len(self.__produit))) for source in sources},
        {tuple(cible for i in range(len(self.__produit))) for cible in cibles})

def test_MonoideGC():
    random.seed(22453)
    mon = PetitMonoideAleatoire(5)
    mon.transformer_graphviz()
    mon.loi_de_composition_to_csv()
    
    mon = MonoideAleatoire(27)
    mon.transformer_graphviz()
    mon.loi_de_composition_to_csv()
    
    
if __name__ == '__main__':
    test_MonoideGC()