Combinaisons, répartitions, distributions, similitudes

Olympiades mathématiques, énigmes et défis
GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 12 Jan 2021, 17:44

J'ai écrit une procédure qui ne repose pas sur itemtools et qui évite de produire toutes les distributions. Ça va beaucoup plus vite sur les gros exemples.

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)
CPU times: user 388 ms, sys: 8.08 ms, total: 396 ms
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)
CPU times: user 10.6 s, sys: 4.4 ms, total: 10.6 s
Wall time: 10.6 s

61435



Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 12 Jan 2021, 23:26

GaBuZoMeu a écrit:J'ai écrit une procédure qui ne repose pas sur itemtools et qui évite de produire toutes les distributions. Ça va beaucoup plus vite sur les gros exemples.

[...]

Code: Tout sélectionner
%time S=Sphere([0,1,2,3,0,0,1,1,0,2,1,1],4)
len(S)
CPU times: user 388 ms, sys: 8.08 ms, total: 396 ms
Wall time: 395 ms

61435


Alors si je comprends bien, à partir d'une distribution, tu crées les distributions qui partagent un certain nombre de valeurs en commun. C'est intéressant ta façon de les créer, je n'avais jamais pensé à ça...

Tu obtiens toutes les distributions possibles ayant d différences avec la distribution ref, en très peu de temps... et le gain de temps c'est parce que tu ne génères que les distributions que tu recherches, pas besoin de toutes les créer puis de filtrer..

Pour la distribution [0,1,2,3,0,0,1,1,0,2,1,1], le nombre de distributions qui ont 8 différences avec est 61435 ? Et elles sont toutes générées en moins d'une seconde c'est impressionnant.

Cette fonction est intéressante, elle permet de matriser la génération à partir d'un paramètre qui est le nombre de différences/similitudes. Je sais (par retour d'expérience) que ce paramètre influence la difficulté mais je ne comprends pas encore parfaitement comment.

Quand je maitriserai tous les paramètres il me faudra une fonction qui génère en les prenant tous en compte :gene:

Merci en tout cas.
Modifié en dernier par Obwil le 13 Jan 2021, 01:06, modifié 1 fois.

GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 13 Jan 2021, 00:52

Pour la distribution [0,1,2,3,0,0,1,1,0,2,1,1], le nombre de distributions qui ont 8 différences avec est 61435 ?

Non, 8 similitudes (ou 4 différences).

GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 15 Jan 2021, 00:41

Je poursuis : une fois qu'on a la procédure "Sphere" ci-dessus, on peut l'utiliser dans une procédure pour la recherche des solutions d'un certain nombre de conditions de similitude, et du coup ça va assez vite.
Je réemploie la procédure
Code: Tout sélectionner
def simil(L,M):
    # calcule le nombre de similitudes entre deux distributions
    return sum(min(L[i],M[i]) for i in range(len(L)))

dans le code suivant, où les conditions de similitude sont données sous forme d'un couple formé d'une distribution et du nombre de similitudes imposé.
Code: Tout sélectionner
def cherche_sol(cond1,*conds) :
    S=Sphere(cond1[0],sum(cond1[0])-cond1[1])
    Sol=[dist for dist in S if \
         all(simil(dist,cond[0])==cond[1] for cond in conds)]
    return Sol


Du coup, ça marche vite. Exemple :
Code: Tout sélectionner
%time L=cherche_sol(([0,1,2,3,0,0,1,1,0,2,1,1],8),\
                  ([2,1,0,1,2,2,0,0,0,1,3,0],7),\
                  ([0,0,3,2,1,1,1,1,2,0,1,0],3),\
                  ([1,2,1,2,1,0,0,0,1,1,2,1],9))

print(L)

CPU times: user 708 ms, sys: 7.23 ms, total: 715 ms
Wall time: 715 ms
[[1, 2, 0, 3, 0, 0, 0, 0, 0, 2, 3, 1], [2, 2, 0, 3, 0, 0, 0, 0, 0, 2, 2, 1]]

Moins d'une seconde pour trouver les deux solutions de ce système de conditions de similitude. À la main, je pense que ça serait trèspénible.

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 15 Jan 2021, 00:53

Je suis bluffé par la vitesse d'exécution..
Les 4 distributions tu les a créées comment?

GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 15 Jan 2021, 11:40

Au hasard pour les trois premières, au pif pour la dernière.

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 15 Jan 2021, 17:44

J'essaie de comparer ton temps de calcul avec mon temps de calcul mais petit problème :

Code: Tout sélectionner
Fatal error: Allowed memory size of 134217728 bytes exhausted


Il faut que j'améliore une de mes fonctions et je reviendrai pour comparer avec ta méthode ;)

EDIT : en fait il faut que j'arrive à traduire ta méthode en PHP c'est exactement ce qu'il me faut.
Encore un merci au passage pour ton aide.

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 16 Jan 2021, 01:43

GaBuZoMeu a écrit:
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



Hello, j'ai essayé de traduire ta première fonction en PHP (sans y rien comprendre pour l'instant), voici le résultat :

Code: Tout sélectionner
function sous($dist, $d){
    $l = count($dist);
    $L = [[]];
    foreach(range(0,$l) as $i){
        $K = [];
        $s = array_sum(array_slice($dist, $i+1));
        foreach($L as $p){
            $q = array_sum($p);
            $m = max($d-$q-$s, 0);
            $M = min($dist[$i], $d-$q);
            foreach(range($m, $M+1) as $j){
                $K[] = $p+[$j];
            }
        }
        $L = $K;
    }
    return $L;
}


Ensuite je l'appelle :
Code: Tout sélectionner
sous([3,2,2,1,1,0], 2)


En résultat je n'obtiens que des tableaux contenant une valeur, soit 0 soit 1 soit 2... je vais trouver d'où vient le problème.

GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 16 Jan 2021, 16:51

Comme je l'ai déjà dit, je ne parle pas le php. Je peux en comprendre des bouts, mais par exemple je ne sais pas bien comment php travaille avec les listes (ou les tableaux). Par exemple, je ne comprends pas ce que fait :
Code: Tout sélectionner
$K[] = $p+[$j]

Une petite embrouille à laquelle il faut faire attention : dans range(3,10), python va de 3 à 9; si j'ai bien compris, php va de 3 à 10.

Je commente mon code
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'entrée dist est une liste d'entiers, l'entrée d est un entier
    l=len(dist) # l = longueur de la liste dist
    L=[[]] # L = liste dont le seul élément est la liste vide ; va
           # devenir une liste de listes d'entiers
    for i in range(l) : # pour i allant de 0 à l-1 inclus
        K=[] # K = liste vide ; va devenir une liste de listes d'entiers
        s=sum(dist[i+1:]) # s = somme des éléments de dist
                          # venant après dist[i]
        for p in L : # pour p parcourant L ;
            q=sum(p) # q = somme des éléments de p
            m=max(d-q-s,0) # m = maximum de d-q-s et 0
            M=min(dist[i],d-q) # M = minimum de dist[i] et d-q
            for j in range(m,M+1) : # pour j allant de m à M (inclus)
                K.append(p+[j]) # ajoute un nouvel élément en fin
                                # de la liste K : la liste entiers
                                # obtenue en ajoutant l'entier j en
                                # fin de la liste p
        L=K
    return L

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 16 Jan 2021, 20:24

GaBuZoMeu a écrit:Comme je l'ai déjà dit, je ne parle pas le php. Je peux en comprendre des bouts, mais par exemple je ne sais pas bien comment php travaille avec les listes (ou les tableaux). Par exemple, je ne comprends pas ce que fait :
Code: Tout sélectionner
$K[] = $p+[$j]

Une petite embrouille à laquelle il faut faire attention : dans range(3,10), python va de 3 à 9; si j'ai bien compris, php va de 3 à 10.

Je commente mon code
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'entrée dist est une liste d'entiers, l'entrée d est un entier
    l=len(dist) # l = longueur de la liste dist
    L=[[]] # L = liste dont le seul élément est la liste vide ; va
           # devenir une liste de listes d'entiers
    for i in range(l) : # pour i allant de 0 à l-1 inclus
        K=[] # K = liste vide ; va devenir une liste de listes d'entiers
        s=sum(dist[i+1:]) # s = somme des éléments de dist
                          # venant après dist[i]
        for p in L : # pour p parcourant L ;
            q=sum(p) # q = somme des éléments de p
            m=max(d-q-s,0) # m = maximum de d-q-s et 0
            M=min(dist[i],d-q) # M = minimum de dist[i] et d-q
            for j in range(m,M+1) : # pour j allant de m à M (inclus)
                K.append(p+[j]) # ajoute un nouvel élément en fin
                                # de la liste K : la liste entiers
                                # obtenue en ajoutant l'entier j en
                                # fin de la liste p
        L=K
    return L


Merci pour ces commentaires ça va m'aider à comprendre parce que même après conversion en PHP ce n'était pas clair lol.
Oui je sais que tu ne pouvais pas m'aider en PHP, je mettais quand même l'update de mon avancement ^^. J'ai obtenu de l'aide sur stackoverflow et il m'ont aidé à bien traduire, ils sont tellement cool sur ce site. Tout comme ce forum, vraiment je me sens tellement reconnaissant envers vous de m'aider à progresser.

Et en fait pour l'instant ta fonction sous() va me suffire pour pouvoir compléter ma méthode ! Et au passage ta fonction est vraiment performante, enfin elle est balaise quoi, faut être calé en math pour pouvoir créer qqch comme ça.. je suis impressionné. Je t'enverrai bientôt mon temps de process, ça peut être intéressant parce que je n'ai pas la même méthode.

EDIT : résultat du temps de génération avec ma procédure : 1325126 ms
J'ai perdu :gene:

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 21 Jan 2021, 12:56

GaBuZoMeu a écrit:J'ai écrit une procédure qui ne repose pas sur itemtools et qui évite de produire toutes les distributions. Ça va beaucoup plus vite sur les gros exemples.
[...]


Salut GaBuZoMeu, je me permets de revenir vers toi pour solliciter tes compétences si tu le veux bien.
J'ai une fonction récursive qui me permet de générer toutes les distributions possibles, à partir d'un nombre de valeurs et de la longueur de la combinaison. Et dès qu'une distribution est créée je l'enregistre dans une table mySQL.

Exemple :
Code: Tout sélectionner
toutes_distributions(nb_valeurs = 4, longueur_combi = 4);

Donnera les combinaisons suivantes :
Code: Tout sélectionner
[0,0,0,4]
[0,0,1,3]
[0,0,2,2]
[0,0,3,1]
[0,0,4,0]
[0,1,0,3]
[0,1,1,2]
...


Cette fonction aboutit à un temps de calcul assez long pour de grandes valeurs, par exemple pour 9 valeurs et une longueur de 9, j'ai généré environ 24000 combinaisons et ça m'a pris plusieurs secondes...

Si tu as une idée de fonction dans le style de tes fonctions précédentes (qui étaient d'une efficacité assez impressionnantes haha), ça m'aiderait beaucoup ;)

GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 21 Jan 2021, 19:32

Avec itertools :

Code: Tout sélectionner
import itertools as it

def convert_dist(comb,long):
    # convertit une combinaison en distribution de longueur long
    bord=[-1]+list(comb)+[len(comb)+long]
    return [bord[i+1]-bord[i]-1 for i in range(len(bord)-1)]

def toutes_dist(long,car) :
    # liste les distributions de longueur long sur car caractères
    combs=it.combinations(range(long+car-1),car-1)
    return [convert_dist(comb,long) for comb in combs]


Longueur 9, 9 valeurs :
Code: Tout sélectionner
%time len(toutes_dist(9,9))

CPU times: user 68 ms, sys: 3.31 ms, total: 71.3 ms
Wall time: 71.9 ms

24310

Sans itertools :
Code: Tout sélectionner
def toutes_dist_bis(long,car) :
    L=[[]]
    for i in range(car-1) :
        K=[]
        for p in L :
            part=sum(p)
            for j in range(long-part+1) :
                K.append(p+[j])
        L=K
    L=[p+[long-sum(p)] for p in L]
    return L


Toujours longueur 9, 9 valeurs :
Code: Tout sélectionner
%time len(toutes_dist_bis(9,9))

CPU times: user 98.6 ms, sys: 3.44 ms, total: 102 ms
Wall time: 101 ms

24310

Même résultat heureusement, un peu plus lent mais compétitif tout de même.

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 21 Jan 2021, 20:15

Wow merci beaucoup pour ton aide et ta réactivité je vais tout de suite la convertir en PHP.
Je suis trop content :D

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 21 Jan 2021, 20:45

C'est bon j'ai réussi à l'écrire en PHP et elle est bien plus rapide que ma précédente !
Merci encore, en plus j'ai compris globalement le fonctionnement donc c'est génial.

GaBuZoMeu
Habitué(e)
Messages: 4096
Enregistré le: 05 Mai 2019, 11:07

Re: Combinaisons, répartitions, distributions, similitudes

par GaBuZoMeu » 22 Jan 2021, 11:18

Avec plaisir.

Obwil
Membre Naturel
Messages: 34
Enregistré le: 13 Juil 2019, 17:14

Re: Combinaisons, répartitions, distributions, similitudes

par Obwil » 22 Jan 2021, 20:29

GaBuZoMeu a écrit:Avec plaisir.


Salut GaBuZoMeu,

J'ai travaillé sur une nouvelle fonction aujourd'hui, qui me donne toutes les répartitions possibles.
Ce que j'entends par répartition c'est par exemple :
Les distributions [2,0,1,1], [1,2,1,0] et [0,1,2,1] ont pour répartition [2,1,1,0] : une valeur 2 fois, deux autres 1 fois et une dernière 0 fois.

Du coup je me suis dit qu'à partir de tes fonctions je devais être en capacité de la créer !
J'ai un peu galéré mais j'ai réussi et la voici, traduite en python :

Code: Tout sélectionner
def toutes_rep(lon,val) :
    L=[]
    for j in range(lon,0,-1) :
        L.append([j])
    for i in range(val-1) :
        K=[]
        for p in L :
            q=min(lon-sum(p),p[-1])
            s=min(1,lon-sum(p))
            for j in range(q,s-1,-1) :
                K.append(p+[j])
        L=K
    return L


EDIT : je viens aussi de traduire ton ensemble de fonctions Sphere en PHP et ça va encore m'aider donc merci encore.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 9 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite