Monoide.py 10 KB
Newer Older
1
2
3
4
5
6
7
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
8
from typing import *
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 :
25
        - identite(self,objet:Any = None) -> Morphisme: renvoie l'element neutre peu import l'objet
26
27
28
        - 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"""
    
29
30
    def __init__(self, nom:str = "Monoide"):
        CategorieLibre.__init__(self,{1},nom)
31
        
32
    def __ior__(self, objets:set) -> "Monoide":
33
34
35
36
37
        if objets == {1}:
            CategorieLibre.__ior__(self,{1})
            return self
        raise Exception("Tentative d'ajout d'un objet à un monoide : "+str(objets))
        
38
    def __isub__(self, objets:set) -> "Monoide":
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
        raise Exception("Tentative de retirer un objet à un monoide : "+str(objets))
        
    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"):
64
        GrapheDeComposition.__init__(self,nom=nom)
65
        Monoide.__init__(self,nom=nom)
66
    
67
    def identite(self, objet:Any = None) -> ElementMonoideGC:
68
69
        return GrapheDeComposition.identite(self,1)
    
70
    def elements(self) -> Generator[Morphisme,None,None]:
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
        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
124
125
126
127
128
129
                        if (c,table[(a,b)]) in table and (c,a) in table:
                            if (table[(c,a)],b) not in table:
                                table[(table[(c,a)],b)] = table[(c,table[(a,b)])]
                            elif table[(table[(c,a)],b)] != table[(c,table[(a,b)])]:
                                associativite_verifiee = False
                                break
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
                    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

166
class MonoideAleatoire(CategorieProduit,Monoide):
167
168
169
170
    """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."""
171
    def __new__(cls, nb_elements:int = random.randint(1,20), nom:str = "Monoïde aléatoire"):
172
173
174
175
        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
176
177
178
            if DEBUG_MONOIDE_ALEATOIRE:
                print("Simplification du nombre d'éléments à "+str(nb_elements))
        petits_monoides = tuple(PetitMonoideAleatoire(x) for x in facteurs_premiers(nb_elements))
179
        instance = CategorieProduit.__new__(cls,*petits_monoides)
180
181
        if DEBUG_MONOIDE_ALEATOIRE:
            print("Fin de création d'un monoïde à "+str(nb_elements)+" éléments")
182
        return instance
183
        
184
185
    def __init__(self, nb_elements:int = random.randint(1,20), nom:str = "Monoïde aléatoire"):
        CategorieProduit.__init__(self,*self)
186
        Monoide.__init__(self,nom)
187
    
188
    def __ior__(self, objets:set) -> 'MonoideAleatoire':
189
        if objets == {tuple(1 for i in range(len(self)))}:
190
191
192
193
            return CategorieLibre.__ior__(self,{tuple(1 for i in range(len(self)))})
        elif objets == {1}:
            return CategorieLibre.__ior__(self,{tuple(1 for i in range(len(self)))})
        raise Exception("Tentative d'ajout d'objet dans un monoide "+str(objets))
194
195
196
197
198
199
200

def test_MonoideGC():
    random.seed(22453)
    mon = PetitMonoideAleatoire(5)
    mon.transformer_graphviz()
    mon.loi_de_composition_to_csv()
    
201
    mon = MonoideAleatoire(7)
202
    mon.transformer_graphviz()
203
    mon.loi_de_composition_to_csv(destination="lois de composition/monoide.csv")
204
205
206
207
    
    
if __name__ == '__main__':
    test_MonoideGC()