Combinaisons, répartitions, distributions, similitudes

Olympiades mathématiques, énigmes et défis
GaBuZoMeu
Habitué(e)
Messages: 3958
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: 30
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: 3958
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: 3958
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: 30
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: 3958
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: 30
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: 30
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: 3958
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: 30
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:

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 12 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