N.B. je travaille ici avec les différences plutôt qu'avec les similitudes (le nombre de différence est la longueur de la distribution moins le nombre de similitudes).
On fixe un nombre d de différences. Partant d'une distribution, on fait la liste des schémas possibles de d différences, et pour chaque schéma de différences on fait la liste des schémas d'ajouts qui compensent.
Exemple partant de la distribution [3,0,2,1,1,0] et de d=2, des schémas possibles de 2 différences sont [2,0,0,0,0,0] ou [0,0,1,0,1,0] (il y en a bien d'autres).
Des schémas possibles d'ajouts qui compensent le schéma de différences [0,0,1,0,1,0] sont [0,0,0,2,0,0] ou [0,1,0,0,0,1] (il y en a bien d'autres).
Si on adopte le schéma de différences [0,0,1,0,1,0] et le schéma d'ajouts [0,0,0,2,0,0] on obtient à partir de la distribution de départ la distribution [3,0,1,3,0,0] qui est à distance 2 (a 7-2=5 similitudes).
- Code: Tout sélectionner
def Sous(dist,d) :
# Étant donné une distribution et un entier d (pour différences),
# retourne la liste des schémas de différences de d possibles
# à partir de la distribution.
l=len(dist)
L=[[]]
for i in range(l) :
K=[]
s=sum(dist[i+1:])
for p in L :
q=sum(p)
m=max(d-q-s,0)
M=min(dist[i],d-q)
for j in range(m,M+1) :
K.append(p+[j])
L=K
return L
- Code: Tout sélectionner
def Ajout(sch) :
# Étant donné un schéma de différences,
# retourne la liste des schéma d'ajouts qui compensent.
l=len(sch); d=sum(sch)
L=[[]]
for i in range(l):
K=[]
for p in L :
q=sum(p)
if sch[i]==0:
if sch[i+1:].count(0)==0 :
K.append(p+[d-q])
else :
for j in range(d-q+1):
K.append(p+[j])
if sch[i]>0 :
K.append(p+[0])
L=K
return L
- Code: Tout sélectionner
def Sphere(dist,d) :
# Ètant donné une distribution dist et un entier d,
# retourne la liste des distributions de même type
# à distance d de dist
l=len(dist)
L=Sous(dist,d)
S=[]
for sch in L :
M=Ajout(sch)
for aj in M :
S.append([dist[i]-sch[i]+aj[i] for i in range(l)])
return S
On peut comparer les performances de la procédure "Sphere" avec celle que j'avais écrite précédemment en utilisant itertools pour ne pas me fouler. Il n'y a pas photo.
- Code: Tout sélectionner
%time S=Sphere([0,1,2,3,0,0,1,1,0,2,1,1],4)
len(S)
Wall time: 395 ms
61435
- Code: Tout sélectionner
%time L=cherche(12,12,([0,1,2,3,0,0,1,1,0,2,1,1],8))
len(L)
Wall time: 10.6 s
61435