#!/usr/bin/python # -*- coding: utf-8 -*- # Pour générer les hyperarbres, nous nous servons de la bijection avec le code de Prüfer : nous génèrerons les mots associés avant de les transformer en hyperarbres # 1) Génération des mots de Prüfer def mots(n,k): """ renvoie la liste des mots sur [1,n] à k lettres EXAMPLES:: sage: mots(3,2) [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] """ L=[] if k == 0: return L elif k ==1: for x in range(n): L=L+[[x+1]] return L else: for x in mots(n, k-1): for y in range(n): L=L+[x+[y+1]] return L def CodesDePrufer(n): """ Renvoie l'ensemble des codes de Prufer des hyperarbres sur n sommets EXAMPLES:: sage: CodesDePrufer(3) [[{{1, 2}}, []], [{{1}, {2}}, [1]], [{{1}, {2}}, [2]], [{{1}, {2}}, [3]]] """ Pruf=[] Part=SetPartitions(n-1).list() longueur=0 for i in range(len(Part)): decompSet=Part[i] longueur=len(decompSet)-1 if longueur==0: Pruf=Pruf+[ [decompSet,[]]] else: motspruf=mots(n,longueur) for j in range(len(motspruf)): Pruf=Pruf + [ [decompSet,motspruf[j]] ] return Pruf # 2) Traduction le code de Prüfer en termes de sous-ensembles def Decodage(x,n): """ Etant donné un code de Prufer, renvoie l'hyperarbre correspondant EXAMPLES:: sage: Decodage(CodesDePrufer(3)[2],3) [{2, 3}, {1, 2}] """ L=[] aux=list(x[0]) sousens=[] for k in range(n): for i in aux : if k in i: sousens=sousens+[i] aux.remove(i) mot=x[1] indice=[] aux=[] for k in range(len(mot)): j=len(sousens)-1 while j>-1: if mot[k] in sousens[j]: aux=aux+[sousens[j]] sousens[j:j+1]=[] j=j-1 k=len(mot)-1 while k>-1: if len(aux)>0: aj=[i for i in aux if mot[k] in i] else: aj=[] if len(aj)>0: L=L+aj for i in aj : indice=[] for l in range(len(aux)): if aux[l]==i: indice=indice+[l] m=len(indice)-1 while m>-1 : aux[indice[m]:indice[m]+1]=[] m=m-1 k=k-1 else: m=len(sousens)-1 L=L+[sousens[m]] sousens[m:m+1]=[] k=k-1 if len(sousens)>0: L=L+[sousens[0]] mot=mot+[n] lg=len(mot) for k in range(len(L)): L[k]=L[k].union(Set([mot[lg-1-k]])) return L def DecodListe(Pruf,n): """ Etant donné une liste de codes de Prufer, renvoie la liste d'hyperarbres associée EXAMPLES:: sage: DecodListe(CodesDePrufer(4),4) [[{1, 2, 3, 4}], [{1, 4}, {1, 2, 3}], [{2, 3, 4}, {1, 2}], [{2, 3, 4}, {1, 3}], [{2, 3, 4}, {1, 4}], [{1, 3, 4}, {1, 2}], [{2, 4}, {1, 2, 3}], [{1, 3, 4}, {2, 3}], [{2, 4}, {1, 3, 4}], [{1, 2, 4}, {1, 3}], [{1, 2, 4}, {2, 3}], [{3, 4}, {1, 2, 3}], [{3, 4}, {1, 2, 4}], [{1, 4}, {1, 3}, {1, 2}], [{2, 4}, {1, 2}, {1, 3}], [{3, 4}, {1, 3}, {1, 2}], [{3, 4}, {1, 4}, {1, 2}], [{1, 4}, {1, 2}, {2, 3}], [{2, 4}, {2, 3}, {1, 2}], [{3, 4}, {2, 3}, {1, 2}], [{3, 4}, {2, 4}, {1, 2}], [{1, 4}, {1, 3}, {2, 3}], [{2, 4}, {2, 3}, {1, 3}], [{3, 4}, {2, 3}, {1, 3}], [{2, 4}, {3, 4}, {1, 3}], [{1, 4}, {1, 3}, {2, 4}], [{2, 4}, {2, 3}, {1, 4}], [{3, 4}, {2, 3}, {1, 4}], [{3, 4}, {2, 4}, {1, 4}]] """ L = [] for x in Pruf: L += [Decodage(x, n)] return L # 4) Génération de l'ensemble des hyperarbres def h(n): """ renvoie la liste des hyperarbres sur n sommets sous forme de liste de liste de liste d'ensemble (hyp=liste d'ensemble) EXAMPLES:: sage: h(3) [[{1, 2, 3}], [{1, 3}, {1, 2}], [{2, 3}, {1, 2}], [{2, 3}, {1, 3}]] """ H = DecodListe(CodesDePrufer(n), n) return H # 5) Ordre et génération du poset def HypInf(x): """ Etant donné un hyperarbre, renvoie la liste des hyperarbres plus petits EXAMPLES:: sage: HypInf(h(3)[2]) {{{1, 2, 3}}} sage: HypInf(h(4)[15]) {{{1, 2}, {1, 3, 4}}, {{3, 4}, {1, 2, 3}}} """ L=Set([]) for i in range(len(x)): j=i+1 while j0: fusion=Set([]) for k in range(len(x)): if k not in [i,j]: S=S.union(Set([x[k]])) for l in x[i].union(x[j]): fusion=fusion.union(Set([l])) T=S.union(Set([fusion])) L=L.union(Set([T])) j=j+1 return L def W(n): ''' Génère le poset des hyperarbres où le minimum a été retiré EXAMPLES:: sage: W(3) Finite poset containing 3 elements sage: W(4) Finite poset containing 28 elements ''' hb=h(n) gen=[] for i in range(len(hb)): if len(hb[i])>1: gen=gen+[Set(hb[i])] rel=[] for i in gen: if len(i)>2: for j in HypInf(i): rel=rel+[[j,i]] P=Poset((gen,rel)) return P def homoln(n): """ Renvoie l'homologie du poset EXAMPLES:: sage: homoln(5) {0: 0, 1: 0, 2: Z^64} """ hyp = W(n) return hyp.order_complex().homology() ############################################################################## ##################### Cas des hyperarbres pointés ###################### ############################################################################## # 1) Définition du pointage et des hyperarbres pointés (se sert de decodliste et codePrüfer) def Pointage(x): """ Etant donné un hyperarbre h renvoie l'ensemble des hyperarbres pointés dont l'hyperarbre sous-jacent est h. EXAMPLES:: sage: Pointage([[{1, 2, 3}], [{1, 3}, {1, 2}], [{2, 3}, {1, 2}], [{2, 3}, {1, 3}]]) [[[{2, 3}, 2], [{1, 2}, 1]], [[{2, 3}, 2], [{1, 2}, 2]], [[{2, 3}, 3], [{1, 2}, 1]], [[{2, 3}, 3], [{1, 2}, 2]]] """ L=[] dbt=x[0] for k in dbt: L=L+[[[x[0],k]]] i=1 while i-1: S=[] for l in x[i]: S=S+[L[j]+[[x[i],l]]] L[j:j+1]=S j=j-1 i=i+1 return L def hp(n): """ renvoie la liste des hyperarbres sur n sommets décorés par Perm sous forme de liste de liste de liste d'ensemble (hyp=liste d'ensemble) EXAMPLES:: sage: hp(3) [{({1, 2, 3}, 1)}, {({1, 2, 3}, 2)}, {({1, 2, 3}, 3)}, {({1, 3}, 1), ({1, 2}, 1)}, {({1, 3}, 1), ({1, 2}, 2)}, {({1, 3}, 3), ({1, 2}, 1)}, {({1, 2}, 2), ({1, 3}, 3)}, {({2, 3}, 2), ({1, 2}, 1)}, {({1, 2}, 2), ({2, 3}, 2)}, {({2, 3}, 3), ({1, 2}, 1)}, {({1, 2}, 2), ({2, 3}, 3)}, {({1, 3}, 1), ({2, 3}, 2)}, {({2, 3}, 2), ({1, 3}, 3)}, {({1, 3}, 1), ({2, 3}, 3)}, {({1, 3}, 3), ({2, 3}, 3)}] """ H = DecodListe(CodesDePrufer(n), n) L = [] for x in H : L += Pointage(x) return [Set([(Set(l[0]), l[1]) for l in ha]) for ha in L] # 2) Définition de la relation d'ordre def HyperarbresInferieurs(tupx): """ Etant donné un hyperarbre pointé, renvoie la liste des hyperarbres plus petit EXAMPLES:: sage: HyperarbresInferieurs(hp(3)[4]) [{({1, 2, 3}, 2)}, {({1, 2, 3}, 1)}] """ x = [(Set(comp[0]),comp[1]) for comp in tupx] L = [] for i in range(len(x)): j = i+1 while j < len(x): S = Set([]) T = Set([]) if x[i][0].intersection(x[j][0]).cardinality() > 0: fusion = Set([]) for k in range(len(x)): if k not in [i,j]: S = S.union(Set([(x[k][0],x[k][1])])) for l in x[i][0].union(x[j][0]): fusion = fusion.union(Set([l])) k = x[i][1] l = x[j][1] if k == l: T = S.union(Set([(fusion, k)])) L += [T] else: T = S.union(Set([(fusion, k)])) S = S.union(Set([(fusion, l)])) L += [S, T] j += 1 return [Set([(Set(l[0]), l[1]) for l in ha]) for ha in L] # 3) Astuces d'écriture def setx(x): """ Réécrit l'hyperarbre sous forme d'ensembles d'ensembles EXAMPLES:: sage: setx(hp(4)[3]) {({1, 2, 3, 4}, 4)} """ return Set([(Set(l[0]), l[1]) for l in x]) def to_tuple(x): """ Réécrit l'hyperarbre sous forme de tuple de paires (tuple,entier) EXAMPLES:: sage: to_tuple(hp(4)[3]) (((1, 2, 3, 4), 4),) """ return tuple([(tuple(l[0]), l[1]) for l in x]) def Relations2(n): return {setx(x): list(HyperarbresInferieurs(x)) for x in hp(n)} # 4) Création du poset def HP(n): """ Renvoie le poset sans bornes des hyperarbres pointés EXAMPLES:: sage: HP(3) Finite poset containing 15 elements """ h = hp(n) return Poset({setx(h[i]):list(HyperarbresInferieurs(h[i])) for i in range(len(h))}) def homol(n): """ Renvoie l'homologie du poset des hyperarbres pointés EXAMPLES:: sage: homol(3) {0: 0, 1: Z^7} """ P = HP(n) return P.order_complex().homology() def PosetEtendu(n): """ Renvoie le poset complété d'un min et d'un max EXAMPLES:: sage: PosetEtendu(3) Finite poset containing 17 elements N.B. : On ne calcule pas son homologie puisqu'elle est triviale """ h = hp(n) P = Poset({ha: HyperarbresInferieurs(ha) for ha in h}, facade=True) rels = [] for i, j in P.cover_relations(): rels += [[to_tuple(j), to_tuple(i)]] for i in P.minimal_elements(): rels += [[to_tuple(i), 1]] for i in P.maximal_elements(): rels += [[0, to_tuple(i)]] elms = [to_tuple(l) for l in h] + [0, 1] return Poset((elms, rels), cover_relations=True, facade=True)