IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Exercice de répartition d'éléments dans des groupes


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Expert confirmé
    Avatar de jurassic pork
    Homme Profil pro
    Bidouilleur
    Inscrit en
    Décembre 2008
    Messages
    4 228
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Bidouilleur
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2008
    Messages : 4 228
    Par défaut Exercice de répartition d'éléments dans des groupes
    Hello,
    voici un problème que j'ai posé dans le forum python de developpez mais pour l'instant je n'ai pas eu de réponse probante :
    A partir d'une liste de flottants, regrouper les flottants par groupes de telle façon que la somme des flottants de chaque groupe ait un écart minimal avec les autres groupes. Le nombre de groupes est fixe.
    Exemple : il y a 19 valeurs de départ qui doivent être "dispatchées" en 6 groupes.
    1
    2
    values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696,
    46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]

    Pour bien voir ce que l'on cherche voici une visualisation dans un classeur Excel :
    Nom : Repartition1.png
Affichages : 123
Taille : 35,7 Ko
    Nom : Repartition2.png
Affichages : 120
Taille : 27,6 Ko

    La seule solution que j'ai trouvé pour l'instant c'est de faire un mélange aléatoire des valeurs de départs et de faire beaucoup d'itérations Les valeurs de départ sont affectées arbitrairement suivant leur indice à un groupe ( 5 groupes de 3 éléments et 1 groupe de 4 éléments).
    Voici mon code en python :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    import time
    import random
     
    start = time.time()
    values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696,
              46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]
    random.seed()
    nbfois = 10000000
    Ngpe = 6
    ecartMax = float('inf')
    t = values
    sumGrpSol = [0]*Ngpe
    grp = [0]*len(t)
    # calcul du nombre d éléments minimum par groupe
    NparGpeMin = len(t) // Ngpe
    # création de la liste des groupes
    for i in range(0,(Ngpe * NparGpeMin)+1):
        grp[i] = 1 + (i  // NparGpeMin)
    for i in range((Ngpe * NparGpeMin),len(t)):
        grp[i] = i - (Ngpe* NparGpeMin) + 1
    for nbf in range(nbfois,-1,-1):
        #print(grp)
        # mélange des valeurs
        random.shuffle(t)
        maxi = 0
        mini = float('inf')
        sumGrp = [0]*Ngpe
        sumGrpt = (0,)*Ngpe
        # calcul de la somme des éléments pour chaque groupe
        for i in range(0,len(t)):
            sumGrp[grp[i] -1] =  sumGrp[grp[i] -1] + t[i]
        ecart = max(sumGrp) - min(sumGrp)
        if ecart < ecartMax:
            ecartMax = ecart
            tres = []
            #Mémorisation sous forme de tuple
            for i in range(0,len(t)):
                tres.append((t[i],grp[i]))
                sumGrpSol = sumGrp.copy()
        if nbf%1000000 == 0:
            print(tres)
            print(ecartMax)
            print(sumGrpSol)
    end = time.time()  
    print('temps écoulé : ' + str(end - start) + " s")
    Dans cet exemple je fais 10000000 d'itérations et j'affiche le résultat tous les 1000000 d'itérations. Avec cette méthode je ne suis pas certain de trouver la solution optimale et cela mets 10 secondes pour 1000000 d'itérations.
    J'ai essayé des fonctions combinatoires python mais le souci c'est que la permutation de 19 éléments c'est 19! = 121,645,100,408,832,000. Balayer tout cela c'est énormément de temps.
    Peut-être faut-il utiliser des fonctions de probabilité ou de statistiques (je ne connais pas ces domaines) pour réduire le temps de calcul ou bien simplifier la recherche.
    Ami calmant, J.P


  2. #2
    Rédacteur/Modérateur

    Avatar de User
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    8 598
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Août 2004
    Messages : 8 598
    Billets dans le blog
    67
    Par défaut Un début de piste
    Bonjour,

    Concernant l'algo, il doit y avoir d'autre possibilités sans utiliser le générateur aléatoire, par exemple :

    On calcule d'abord une estimation de la somme attendue par groupe :

    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    somme_groupe = sum([values])/nb_groupes

    Ensuite, on recherche les sous-ensembles de valeurs dont la somme vaut somme_groupe à plus ou moins un écart près :

    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    if abs(sum(subset)-somme_groupe)<=ecart then
        '...

    En fait on explore un arbre binaire, et on arrête la recherche sur une branche dès que la somme partielle est supérieure à somme_groupe + ecart.

    Une fois le subset trouvé on enlève les nombres qui le composent de la liste values.

    On répète la procédure pour (nb_groupes-1) groupes en ajoutant à chaque fois un nouveau subset (groupe).

    Le dernier groupe étant formé des nombres restant dans values.

    Le souci, c'est qu'il peut y avoir des séries de valeurs pour lesquels ça peut durer..

    J'ai écrit ce code Python pour le tester :

    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    def gen_subsets(sous_ensembles, element,somme_groupe):
        # fonction permettant de générer les nouveaux sous-ensembles après ajout de l'élément
     
        # parcours des sous-ensembles (subset)
        for subset in sous_ensembles:
     
            # ordre de renvoyer le sous-ensemble : descente à gauche dans l'arbre binaire
            yield subset
     
            # création du nouveau sous-ensemble avec ajout du nouvel élément
            new_subset = tuple(subset) + (element,)
     
            # ordre de renvoyer le nouveau sous-ensemble  : descente à droite dans l'arbre binaire
            if sum(new_subset)<=somme_groupe:
                yield new_subset
     
     
    def generateur_subsets(elements,somme_groupe):
        # permet de génèrer les sous-ensembles à partir de l'ensemble de départ
     
        # tri des éléments de l'ensemble de départ
        # elements.sort()
     
        # initialisation de la variable sous_ensembles avec un élément vide : {{}}
        sous_ensembles = iter([()])
     
        # parcours des éléments de la liste de départ
        for ei in elements:
            # on génère les nouveaux sous-ensembles après ajout de ei
            sous_ensembles = gen_subsets(sous_ensembles, ei, somme_groupe)
     
        # renvoie la générateur permettant de parcourir les sous-ensembles obtenus
        return sous_ensembles
     
     
    values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696,
           46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]
     
    # nombre de groupes
    nb_groupes = 6
     
    ecart = 0.0
     
    somme_groupe = sum(values)/nb_groupes
     
    print(somme_groupe)
     
    # parcours des écarts : 0.0, 0.1, 0.2, ..., 10
    while ecart<=10:
        # initialisation
        nombres = values[:]
        groupes = []
     
        # parcours des groupes : 0, 1, ..., k-2
        for i in range(nb_groupes-1):
     
            # parcours des sous-ensembles
            for subset in generateur_subsets(nombres, somme_groupe+ecart):
     
                # si la somme des entiers du sous-ensemble subset est égale somme_groupe plus ou moins l'écart
                if (abs(sum(subset)-somme_groupe)<=ecart):
                   # ajout du sous-ensemble de nombres
                    groupes.append(subset)
                    for v in subset:
                        nombres.remove(v)
                    break
     
            # si pas de subset de trouvé
            if len(groupes)==i:
                break # sortie de la boucle
     
        # si groupes formés        
        if len(groupes)>i:
             break # sortie de la boucle
     
        ecart=ecart + 0.1 # incrémentation de l'écart pour une recherche
     
    groupes.append(tuple(nombres)) # ajout du dernier groupe dans la liste
     
    print(groupes)
     
    sums_groupes = [sum(g) for g in groupes]
     
    print(sums_groupes)
     
    ecart_max = max(sums_groupes) - min(sums_groupes)
     
    print("ecart max. = " + str(ecart_max))

    Je me suis fixé comme limite un écart maxi. de 10 par rapport à la somme des valeurs attendue par groupe.

    Il doit y avoir d'autres possibilités mais j'en connais pas plus, les experts du forum algo pourront t'en dire plus.

    Cdlt,
    Vous trouverez dans la FAQ, les sources ou les tutoriels, de l'information accessible au plus grand nombre, plein de bonnes choses à consulter sans modération

    Des tutoriels pour apprendre à créer des formulaires de planning dans vos applications Access :
    Gestion sur un planning des présences et des absences des employés
    Gestion des rendez-vous sur un calendrier mensuel


    Importer un fichier JSON dans une base de données Access :
    Import Fichier JSON

  3. #3
    Expert confirmé
    Avatar de jurassic pork
    Homme Profil pro
    Bidouilleur
    Inscrit en
    Décembre 2008
    Messages
    4 228
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Bidouilleur
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2008
    Messages : 4 228
    Par défaut
    merci beaucoup User, il m'a l'air sacrément efficace ton algoritme ! je fais faire quelques tests complémentaires pour voir si cela fonctionne avec d'autres paramètres et je mettrai la discussion en résolu.
    Ami calmant, J.P

  4. #4
    Expert confirmé
    Avatar de jurassic pork
    Homme Profil pro
    Bidouilleur
    Inscrit en
    Décembre 2008
    Messages
    4 228
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Bidouilleur
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2008
    Messages : 4 228
    Par défaut
    oops j'avais oublié de préciser une chose c'est qu'il faut un minimum d'éléments dans un groupe ( dans l'exemple 3) et un maximum d'éléments ( 4)
    [EDIT] bon je crois que j'ai trouvé une solution :
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     
    minElem = 3
    maxElem = 4
    # ......
            for subset in generateur_subsets(nombres, somme_groupe+ecart):
     
                # si la somme des entiers du sous-ensemble subset est égale somme_groupe plus ou moins l écart
                if (abs(sum(subset)-somme_groupe)<=ecart):
                    # test pour savoir si il y au moins minElem dans le subset et au plus maxElem
                    if len(subset) >=  minElem and len(subset) <= maxElem:
                   # ajout du sous-ensemble de nombres
                         groupes.append(subset)
                        for v in subset:
                            nombres.remove(v)
                        break

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 221
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 221
    Par défaut
    Zut ... je n'ai pas appliqué la nouvelle contrainte (tous les groupes doivent contenir au moins 3 éléments) ; on doit pouvoir ajouter le test en question, sans que ça change vraiment la performance. La solution donnée par la version actuelle ne respecte pas cette contrainte.

    J'ai fait ça en Windev, je sais que tu connais. Evidemment, ce n'est pas très performant, mais c'est un choix. En 38secondes, j'explore TOUTES les possibilités (en excluant celles qui vont amener à des solutions peu performantes).

    Déclaratives globales :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    un_scenar est une Structure 
    	tt est un tableau de 19 entiers sans signe sur 1 octet
    	sumtt est un tableau de 6 réels
    	nB_placés  est un entier 
    	nMax_non_vide est un entier 
    FIN
    Tbval est un tableau de 19 réels
    Procédures :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    PROCÉDURE calcule_score(qscenar est un_scenar)
     
    Smin, Smax est un réel 
    i est un entier 
    Smin = 9999999999
    Smax = 0
     
    POUR i = 1 À 6 
    	SI qscenar.sumtt[i] < Smin ALORS Smin =  qscenar.sumtt[i]
    	SI qscenar.sumtt[i] > Smax ALORS Smax =  qscenar.sumtt[i]
    FIN
    RENVOYER Smax - Smin
    Code du bouton 'Go' :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    n, i , j    , jmin  , tmax  est un entier
    sum_min , Sum19  , Moy6 , Plafond  est un réel 
    Best_scenar est un_scenar
    Qscenar , newscenar , zzscenar  est un_scenar 
    Tbscenar est un tableau de un_scenar 
    qscore , best_score est un réel 
    pb est un booléen
    ch est une chaîne
    dh1 , dh2  est une DateHeure 
     
    ch = "56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696, 46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786"
     
    POUR TOUTE CHAÎNE sCh DE ch SEPAREE PAR ","
    	i = i+1 
    	Tbval[i]=Val(sCh) 
    	Sum19 = Sum19 + Tbval[i]  	
    FIN
    Moy6 = Sum19 / 6 
    Trace ( " la somme ideale pour chaque groupe est de " , Moy6 )
     
    TableauTrie(Tbval,ttDécroissant)  // pas obligatoire, mais ça aide à faire en sorte que dès la première solution cherchée, on tombe sur une solution performante.
    POUR i = 1 À 19
    	Trace(Tbval[i])
    FIN
     
    dh1 = DateHeureSys()
    POUR i = 1 À 19
    	sum_min = 999999999	
    	POUR j = 1 À 6 
    		SI Best_scenar.sumtt[j] < sum_min ALORS 
    			jmin = j 
    			sum_min = Best_scenar.sumtt[j]
    		FIN
    	FIN
    	Best_scenar.tt[i] = jmin 
    	Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[i]
    FIN
    best_score = calcule_score ( Best_scenar )  
    Trace ( " A ce niveau, on a une valeur  de référence")
    affiche_resu ( Best_scenar, best_score )
    Plafond =  Moy6 + 5 * best_score / 6 
    Trace ( " On peut chercher d'autres solutions, mais dès qu'un des 6 groupes va dépasser " , Plafond, " cette solution ne peut être meilleure que la solution actuelle ")
     
    Qscenar.tt[1] = 1
    Qscenar.sumtt[1] = Tbval[1]
    Qscenar.nB_placés = 1 
    Qscenar.nMax_non_vide = 1 
    TableauAjouteLigne(Tbscenar, Qscenar ) 
     
    TANTQUE TableauOccurrence(Tbscenar) > 0 
    	n = TableauOccurrence(Tbscenar)
    	Qscenar = Tbscenar[n]
    	TableauSupprime(Tbscenar, n )
    	tmax = Qscenar.nMax_non_vide+1
    	SI tmax > 6 ALORS tmax = 6 
    	POUR j = 1 À tmax 
    		newscenar = Qscenar
    		newscenar.tt[Qscenar.nB_placés+1] = j
    		newscenar.sumtt[j] = newscenar.sumtt[j] +Tbval[ Qscenar.nB_placés+1 ]
    		SI newscenar.sumtt[j] < Plafond ALORS 
    			newscenar.nB_placés = Qscenar.nB_placés+1
    			SI j >  newscenar.nMax_non_vide ALORS newscenar.nMax_non_vide = j 
     
    			SI newscenar.nB_placés < 19 ALORS 
    				TableauAjouteLigne( Tbscenar, newscenar ) 
    			SINON
    				qscore = calcule_score (  newscenar )  
    				SI qscore < best_score ALORS 
    					best_score = qscore 
    					Best_scenar = newscenar
    					Plafond =  Moy6 + 5 * best_score / 6 
    					// Je vire tous les scénarios en attente qui ne sont plus compétitifs 
    					POUR ii = TableauOccurrence(Tbscenar) À 1 PAS - 1 
    						zzscenar = Tbscenar[ii]						
    						pb = Faux 
    						POUR jj = 1 À 6 
    							SI zzscenar.sumtt[jj] > Plafond ALORS pb = Vrai 
    						FIN
    						SI pb ALORS 
    							//trace ( " suppression scenar n°" , ii )
    							TableauSupprime(Tbscenar, ii  )
    						FIN
    					FIN
    					//info( " ok   on a amélioré ")
    				FIN
    			FIN
    		FIN
    	FIN
    FIN
    dh2 = DateHeureSys() 
    Trace ( " Résultat final " )
    affiche_resu ( Best_scenar, best_score )
    Info ( " fini" , DateHeureDifférence( dh1, dh2 ))

  6. #6
    Expert confirmé
    Avatar de jurassic pork
    Homme Profil pro
    Bidouilleur
    Inscrit en
    Décembre 2008
    Messages
    4 228
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Bidouilleur
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2008
    Messages : 4 228
    Par défaut
    Merci bien Tbc92, j'ai toujours un windev 16 sous le coude, je vais essayer ton code. Tu as oublié de mettre la procédure affiche_résu

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Doublons dans des groupes
    Par tassia dans le forum Débutez
    Réponses: 3
    Dernier message: 03/10/2012, 13h02
  2. [GRAPH] BOXPLOT : relier les moyennes de observée dans des groupes / BOXCONNECT
    Par Malex_SAS dans le forum ODS et reporting
    Réponses: 1
    Dernier message: 04/11/2011, 09h04
  3. Tris dans des Groupes
    Par Pirad13 dans le forum BIRT
    Réponses: 4
    Dernier message: 14/03/2011, 10h35
  4. Récuperer les comptes utilisateurs dans des groupes
    Par Ludo75 dans le forum VBScript
    Réponses: 3
    Dernier message: 08/06/2009, 18h49
  5. Répartition dans des groupes
    Par Celelibi dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 15/11/2008, 00h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo