monoïde

Pour les nœuds, l'attribut 'L' joue un autre rôle, c'est un raccourci obligatoire de distance nulle. Faisant que toute action aboutissant sur un nœud 'x', dont l'attribut 'L' est différent de zéro, aboutit en fait et de façons immédiate et systématique sur le nœud 'x.L'. Ce type de comportement qui s'implémente récursivement dans différentes fonctions s'appelle un aspect.

Créer une seconde fonction 'move' et une seconde fonction 'build_path' qui tiennent compte de cet aspect

Très bien. Tu introduis ici la notion d’aspect, où chaque nœud peut pointer vers un raccourci (alias) via `L`, et toute action ou navigation vers un nœud doit s’effectuer après résolution de ce raccourci.

On va donc créer deux nouvelles fonctions :

move_aspect(`x`, label) — qui applique move après avoir suivi récursivement tous les raccourcis `L`
build_path_aspect(`x`, word) — qui applique build_path en tenant compte de l’aspect à chaque étape

Fonction utilitaire d’aspect : aspect(`x`)

Avant cela, voici une fonction pour suivre récursivement les raccourcis `L` jusqu'à un nœud stable :

def aspect(x):
    """Retourne le nœud final en suivant récursivement les raccourcis L."""
    while x != 0 and M[x]['L'] != 0:
        x = M[x]['L']
    return x

Nouvelle move_aspect(`x`, label)

def move_aspect(x, label):
    """Suit l’arête 'a' ou 'b' depuis le nœud x en tenant compte des raccourcis d’aspect."""
    x = aspect(x) # Appliquer l’aspect d’entrée
    if label not in ('a', 'b'):
        raise ValueError("label doit être 'a' ou 'b'")

    y = M[x][label]

    if y == 0:
        # Fils inexistant → allocation
        y = alloc()
        if y == 0:
            raise RuntimeError("Plus de cellules libres disponibles")
        M[x][label] = y
        M[y]['d'] = M[x]['d'] + 1

    return aspect(y) # Appliquer l’aspect de sortie

Nouvelle build_path_aspect(`x`, word)

def build_path_aspect(x, word):
    """
    Suit et construit un chemin selon le mot, en tenant compte des raccourcis d’aspect à chaque étape.
    """
    x = aspect(x) # Aspect du point de départ
    for c in word:
        if c not in ('a', 'b'):
            raise ValueError("Le mot ne doit contenir que les lettres 'a' et 'b'")
        x = move_aspect(x, c)
    return x

Exemple d’utilisation :

n = build_path_aspect(1, 'abaabb')
print(f"Nœud final avec aspect : M[{n}]")

Résumé :

Les raccourcis via `L` sont automatiquement pris en compte à chaque étape.
L’aspect est résolu à l’entrée et à la sortie de chaque déplacement.
Ces fonctions permettent de gérer un graphe compressé (avec des fusions ou identifications de nœuds via `L`), sans casser la logique du monoïde.

Souhaites-tu une fonction pour fusionner deux nœuds en utilisant `L` comme raccourci canonique ?

Il est utile de choisir les noms de fonction ou de laisser l'IA en choisir d'autres plus court et davantage mémothechnique.

Redonne le programme complet en renommant les fonctions de façon plus courte et plus française

Voici le programme complet avec des noms de fonctions plus courts et en français, comme demandé. Toutes les fonctions précédentes sont incluses, avec une terminologie unifiée..

Définition, initialisation et fonctions utilitaires

import numpy as np
# Type structuré pour chaque cellule
cellule_dtype = np.dtype([
    ('a', np.uint32), # Fille selon 'a'
    ('b', np.uint32), # Fille selon 'b'
    ('d', np.uint32), # Profondeur
    ('L', np.uint32), # Raccourci (ou cellule libre suivante)
    ('u', np.uint16) # 16 bits de flags
])

# Création du tableau
N = 100_000
M = np.zeros(N, dtype=cellule_dtype)

# Initialisation des cellules libres
for i in range(1, N - 1):
    M[i]['L'] = i + 1
M[N - 1]['L'] = 0

# Variable globale : tête de la liste libre
L = 1

# Création du neutre en M[1]
e = L
L = M[L]['L']
M[e]['L'] = 0
M[e]['a'] = 0
M[e]['b'] = 0
M[e]['d'] = 0
M[e]['u'] = 1 # u₀ = 1 => occupé

Accès aux bits de `u`

def lire_bit(x, i):
    return (M[x]['u'] >> i) & 1
def ecrire_bit(x, i, val):
    if val:
        M[x]['u'] |= (1 << i)
    else:
        M[x]['u'] &= ~(1 << i)

def inverser_bit(x, i):
    M[x]['u'] ^= (1 << i)

Allocation et libération

def allouer():
    global L
    if L == 0:
        return 0
    x = L
    L = M[x]['L']
    M[x]['a'] = 0
    M[x]['b'] = 0
    M[x]['d'] = 0
    M[x]['L'] = 0
    M[x]['u'] = 0
    ecrire_bit(x, 0, 1)
    return x
def liberer(x):
    global L
    M[x]['a'] = 0
    M[x]['b'] = 0
    M[x]['d'] = 0
    M[x]['u'] = 0
    M[x]['L'] = L
    L = x

Aspect (raccourcis)

def aspect(x):
    while x != 0 and M[x]['L'] != 0:
        x = M[x]['L']
    return x

Navigation simple et aspectuelle

def aller(x, voie):
    if voie not in ('a', 'b'):
        raise ValueError("voie doit être 'a' ou 'b'")
    y = M[x][voie]
    if y == 0:
        y = allouer()
        if y == 0:
            raise RuntimeError("Plus de cellules libres")
        M[x][voie] = y
        M[y]['d'] = M[x]['d'] + 1
    return y
def aller_aspect(x, voie):
    x = aspect(x)
    if voie not in ('a', 'b'):
        raise ValueError("voie doit être 'a' ou 'b'")
    y = M[x][voie]
    if y == 0:
        y = allouer()
        if y == 0:
            raise RuntimeError("Plus de cellules libres")
        M[x][voie] = y
        M[y]['d'] = M[x]['d'] + 1
    return aspect(y)

Chemins simples et aspectuels

def chemin(x, mot):
    for c in mot:
        if c not in ('a', 'b'):
            raise ValueError("Le mot ne contient que 'a' ou 'b'")
        x = aller(x, c)
    return x
def chemin_aspect(x, mot):
    x = aspect(x)
    for c in mot:
        if c not in ('a', 'b'):
            raise ValueError("Le mot ne contient que 'a' ou 'b'")
        x = aller_aspect(x, c)
    return x

Exemple de test

# Créer le chemin 'abaab' depuis le neutre en tenant compte des raccourcis
x = chemin_aspect(1, 'abaab')
print(f"Chemin 'abaab' mène à M[{x}], profondeur {M[x]['d']}")

Souhaites-tu maintenant que j’ajoute une fonction fusionner`(x,y)` qui établit un raccourci entre deux nœuds ?

Oui

Voici la fonction fusionner`(x, y)` qui établit un raccourci (via `L`) entre deux nœuds `x` et `y`, en les considérant comme représentant le même élément du monoïde :

def fusionner(x, y):
    """
    Fusionne les nœuds M[x] et M[y] :
    établit un raccourci du plus grand index vers le plus petit.
    Fusionne récursivement leurs fils respectifs.
    """
    x = aspect(x)
    y = aspect(y)
    if x == y or x == 0 or y == 0:
        return

    u = min(x, y)
    v = max(x, y)

    # v devient un raccourci vers u
    M[v]['L'] = u

    # Fusion récursive des fils 'a'
    if M[u]['a'] != 0 or M[v]['a'] != 0:
        if M[u]['a'] == 0:
            M[u]['a'] = M[v]['a']
        elif M[v]['a'] == 0:
            M[v]['a'] = M[u]['a']
        else:
            fusionner(M[u]['a'], M[v]['a'])

    # Fusion récursive des fils 'b'
    if M[u]['b'] != 0 or M[v]['b'] != 0:
        if M[u]['b'] == 0:
            M[u]['b'] = M[v]['b']
        elif M[v]['b'] == 0:
            M[v]['b'] = M[u]['b']
        else:
            fusionner(M[u]['b'], M[v]['b'])

Règles de fusion :

On applique l’aspect aux deux nœuds avant toute action.
Si `x` == `y`, ou si un des deux est nul (0), on ne fait rien.
Le nœud avec le plus grand index (`v`) devient raccourci vers celui de plus petit index (`u`).
On fusionne récursivement leurs fils `a` et `b` si nécessaire.

Exemple d’utilisation :

a1 = chemin_aspect(1, 'ab')
a2 = chemin_aspect(1, 'ba')
fusionner(a1, a2)

Ceci crée une identification entre les deux éléments `ab` et `ba` dans le monoïde.

Souhaites-tu aussi une fonction de réduction canonique d’un nœud, ou un affichage graphique du graphe (via Graphviz par exemple) ?

Complète la fonction 'fusionner' afin qu'elle recalcule la profondeur des noeuds parcourus.

Voici la version complétée de la fonction fusionner(x, y) qui, en plus d’établir les raccourcis et de fusionner les sous-arbres, recalcule la profondeur minimale de tous les nœuds concernés.

Règle de recalcul :

La profondeur d’un nœud est égale à 1 + profondeur du père.
Lorsqu’un raccourci est créé ou qu’un nœud est relié, la profondeur réelle peut être réduite, donc on doit propager la nouvelle profondeur aux descendants.

Nouvelle fonction utilitaire pour mise à jour récursive des profondeurs :

def recalculer_profondeur(x, profondeur):
    """Met à jour la profondeur de x et propage si nécessaire à ses enfants."""
    x = aspect(x)
    if x == 0 or M[x]['d'] == profondeur:
        return
    M[x]['d'] = profondeur
    if M[x]['a']:
        recalculer_profondeur(M[x]['a'], profondeur + 1)
    if M[x]['b']:
        recalculer_profondeur(M[x]['b'], profondeur + 1)

Nouvelle version complète de fusionner :

def fusionner(x, y):
    """
    Fusionne les nœuds M[x] et M[y] :
    établit un raccourci du plus grand index vers le plus petit.
    Fusionne récursivement leurs fils respectifs et recalcule les profondeurs.
    """
    x = aspect(x)
    y = aspect(y)
    if x == y or x == 0 or y == 0:
        return

    u = min(x, y)
    v = max(x, y)

    # Créer le raccourci
    M[v]['L'] = u

    # Fusion des fils 'a'
    if M[u]['a'] != 0 or M[v]['a'] != 0:
        if M[u]['a'] == 0:
            M[u]['a'] = M[v]['a']
        elif M[v]['a'] == 0:
            pass # M[u]['a'] est déjà correct
        else:
            fusionner(M[u]['a'], M[v]['a'])

    # Fusion des fils 'b'
    if M[u]['b'] != 0 or M[v]['b'] != 0:
        if M[u]['b'] == 0:
            M[u]['b'] = M[v]['b']
        elif M[v]['b'] == 0:
            pass # M[u]['b'] est déjà correct
        else:
            fusionner(M[u]['b'], M[v]['b'])

    # Recalculer les profondeurs descendantes à partir de u
recalculer_profondeur(u, M[u]['d'])

Exemple :

a1 = chemin_aspect(1, 'aba')
a2 = chemin_aspect(1, 'bab')
fusionner(a1, a2)
# Vérifier que la profondeur a bien été mise à jour
print("Nouvelle profondeur :", M[aspect(a1)]['d'])

Souhaites-tu une fonction qui parcourt tout le graphe pour recalculer globalement toutes les profondeurs atteignables ?

La solution proposée par l'IA n'est pas performante. Il est possible de fusionner les noeuds en respectant les fusions précédentes et en recalculant les profondeurs des noeuds parcourus par l'arlgorithme.

Un algorithme plus performant qui applique l'aspect (utilise les raccourcis déjà présents) et qui calcule les profondeurs en même temps qu'il propage la fusion aux descendants

Très bien. Pour un algorithme plus performant de fusion avec recalcul des profondeurs, on peut procéder de manière itérative et contrôlée, en appliquant l’aspect à chaque étape et en propageant les fusions et les profondeurs en même temps, sans double parcours.

Stratégie :

On maintient une pile de paires de nœuds à fusionner, initialisée avec `(x, y)`.
Pour chaque paire `(x, y)` :
1. On applique aspect(`x`) et aspect(`y`) pour pointer vers les représentations canoniques.
2. Si `x ≠ y`, on fusionne : le plus grand devient raccourci vers le plus petit.
3. On récupère les fils respectifs `(a, b)` et on ajoute à la pile `(f1, f2)` les paires à fusionner.
4. On met à jour immédiatement la profondeur du fils.

Ce processus garantit une seule visite par nœud, et tous les effets sont propagés récursivement de façon contrôlée, sans appel récursif Python, donc plus stable et rapide.

Fonction : fusionner_profond`(x, y)`

def fusionner_profond(x, y):
    """
    Fusionne deux nœuds en propageant les raccourcis et en recalculant les profondeurs,
    tout en appliquant l’aspect à chaque étape. Version itérative.
    """
    pile = [(x, y)]

    while pile:
        x, y = pile.pop()

        x = aspect(x)
        y = aspect(y)

        if x == y or x == 0 or y == 0:
            continue

        u = min(x, y)
        v = max(x, y)

        # Établir le raccourci
        M[v]['L'] = u

        # Profondeur de base pour les descendants
        d_parent = M[u]['d']

        # Traitement pour 'a'
        a1 = M[u]['a']
        a2 = M[v]['a']

        if a1 == 0 and a2 != 0:
            M[u]['a'] = a2
            a1 = a2
        elif a1 != 0 and a2 != 0:
            pile.append((a1, a2))

        if a1 != 0:
            a1_final = aspect(a1)
            if M[a1_final]['d'] != d_parent + 1:
                M[a1_final]['d'] = d_parent + 1

        # Traitement pour 'b'
        b1 = M[u]['b']
        b2 = M[v]['b']

        if b1 == 0 and b2 != 0:
            M[u]['b'] = b2
            b1 = b2
        elif b1 != 0 and b2 != 0:
            pile.append((b1, b2))

        if b1 != 0:
            b1_final = aspect(b1)
            if M[b1_final]['d'] != d_parent + 1:
                M[b1_final]['d'] = d_parent + 1

Exemple d’utilisation

x = chemin_aspect(1, 'abab')
y = chemin_aspect(1, 'baab')

fusionner_profond(x, y)

print("Fusion terminée.")
print("Profondeur commune :", M[aspect(x)]['d'])

Avantages de cette version :

Gère les raccourcis dynamiquement via aspect()
Ne fait aucun appel récursif Python
Calcule et propage les profondeurs exactes en même temps que les fusions
Robuste à des milliers de fusions sans stack overflow

Souhaites-tu une version optimisée avec marquage des nœuds déjà fusionnés pour éviter des tests répétés ?

Lors de la fusion, on choisit bien le noeud d'indice le plus élevé pour lui donner le raccourcis vers le noeud d'indice le moins élevé (afin d'économiser l'accroissement des indices). Mais l'ordre des profondeurs ne respectant pas forcement l'ordre des indices, lors de la fusion de deux noeuds il faut modifier la profondeur des deux noeuds en leur affectant la plus petite profondeur des deux noeuds, et propager la fusion et ces deux profondeurs en même temps.

Très bien. Tu soulèves une subtilité importante :
l’indice le plus petit est utilisé comme représentant canonique pour le raccourci (`L`),
mais la profondeur logique d’un élément du monoïde est indépendante de son indice.

Objectif mis à jour :

Lors de la fusion de deux nœuds `x` et `y` :

on établit le raccourci du plus grand indice vers le plus petit (`v"."L = u`);
on choisit la plus petite profondeur entre `x` et `y`, et on affecte cette profondeur :
- au représentant `u`,
- à l'autre `v`,
- à tous les descendants fusionnés récursivement.

On va donc propager une profondeur cible `d` qui est la profondeur minimale entre `M[x]"."d` et `M[y]"."d`, et s’assurer que tous les descendants fusionnés soient mis à `d"+"1`, `d"+"2`, etc.

✅ Version améliorée : fusionner_profond_v2(`x, y`)

def fusionner_profond_v2(x, y):
    """
    Fusionne deux nœuds M[x] et M[y] en appliquant les raccourcis et
    en assignant à chaque nœud fusionné la plus petite profondeur rencontrée.
    Version itérative avec propagation synchronisée de la profondeur.
    """
    pile = [(x, y)]

    while pile:
        x, y = pile.pop()

        x = aspect(x)
        y = aspect(y)

        if x == y or x == 0 or y == 0:
            continue

        u = min(x, y)
        v = max(x, y)

        # Établir le raccourci v → u
        M[v]['L'] = u

        # Profondeur minimale à propager
        d = min(M[x]['d'], M[y]['d'])
        if M[u]['d'] != d:
            M[u]['d'] = d
        if M[v]['d'] != d:
            M[v]['d'] = d # utile si raccourci suivi plus tard pour d'autres calculs

        # Fils a : propager la fusion
        a1 = M[x]['a']
        a2 = M[y]['a']
        if a1 == 0 and a2 != 0:
            M[u]['a'] = a2
            a1 = a2
        elif a2 == 0 and a1 != 0:
            # Pas besoin de changer M[u]['a'], c'est déjà bon
            pass
        elif a1 != 0 and a2 != 0:
            pile.append((a1, a2))

        if M[u]['a'] != 0:
            z = aspect(M[u]['a'])
            if M[z]['d'] > d + 1:
                M[z]['d'] = d + 1

        # Fils b : même traitement
        b1 = M[x]['b']
        b2 = M[y]['b']
        if b1 == 0 and b2 != 0:
            M[u]['b'] = b2
            b1 = b2
        elif b2 == 0 and b1 != 0:
            pass
        elif b1 != 0 and b2 != 0:
            pile.append((b1, b2))

        if M[u]['b'] != 0:
            z = aspect(M[u]['b'])
            if M[z]['d'] > d + 1:
                M[z]['d'] = d + 1

Construction de monoïdes bigènes

4) Les fusion de noeuds

Fonction utilitaire d’aspect : aspect(`x`)

Nouvelle move_aspect(`x`, label)

Nouvelle build_path_aspect(`x`, word)

Exemple d’utilisation :

Résumé :

Définition, initialisation et fonctions utilitaires

Accès aux bits de `u`

Allocation et libération

Aspect (raccourcis)

Navigation simple et aspectuelle

Chemins simples et aspectuels

Exemple de test

Règles de fusion :

Exemple d’utilisation :

Règle de recalcul :

Nouvelle fonction utilitaire pour mise à jour récursive des profondeurs :

Nouvelle version complète de fusionner :

Exemple :

Stratégie :

Fonction : fusionner_profond`(x, y)`

Exemple d’utilisation

Avantages de cette version :

Objectif mis à jour :

✅ Version améliorée : fusionner_profond_v2(`x, y`)