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 :

Sous-ensemble de valeurs dont la somme est nulle


Sujet :

Algorithmes et structures de données

  1. #1
    Rédacteur/Modérateur

    Avatar de Jean-Philippe André
    Homme Profil pro
    Developpeur VBA, C# et VB.Net =]
    Inscrit en
    juillet 2007
    Messages
    14 127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Developpeur VBA, C# et VB.Net =]
    Secteur : Finance

    Informations forums :
    Inscription : juillet 2007
    Messages : 14 127
    Points : 32 252
    Points
    32 252
    Par défaut Sous-ensemble de valeurs dont la somme est nulle
    Bonjour à tous,

    j'ai une demande de traitement qui semble prendre une éternité quel que soit le bout par lequel je la prends.

    Je dispose d'un ensemble de valeurs positives ou négatives, dont le nombre peut aller à 150+, mais je me limite pour l'instant à 50 valeurs.

    Exemples simplifiés (3,5,-2,-8,14,2) qui devrait me sortir (3,5,-8) et (-2,2)
    ou encore
    (2,-2,2) qui me sortira (2,-2)

    Une valeur ne sert qu'à un seul sous-ensemble, ou peut ne pas être appariable.

    J'ai bien tenté de diminuer les valeurs en éliminant les extremes non appariables, mais avec des sous-ensemble allant jusque 18 valeurs, ca picote sévère.

    La demande originale concerne VBA, mais je m'oriente vers le Python pour essayer d'aboutir à un temps de traitement raisonnable.
    Si vous avez des suggestions, je suis preneur
    Merci
    Cycle de vie d'un bon programme :
    1/ ca fonctionne 2/ ca s'optimise 3/ ca se refactorise

    Pas de question technique par MP, je ne réponds pas

    Apprendre à programmer avec Access 2016 et Access 2019

    Pensez à consulter la FAQ Excel et la FAQ Access

    Derniers tutos
    Excel et les paramètres régionaux
    Les fichiers Excel binaires : xlsb,

    Autres tutos

  2. #2
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 627
    Points : 11 564
    Points
    11 564
    Par défaut
    Bonjour

    • Tout d'abord, ce que tu cherches à faire est compliqué. 2150+ possibilités d'associations.
    • Ensuite, c'est un cas où la méthode utilisée compte énormément. Pourtant, tu ne donnes aucun élément sur la méthode que tu as employée.
    • D'autre part, 18 nombres, c'est trop petit pour que tu commences à expérimenter des difficultés.


    Les conseils :
    • Séparer valeurs positives et négatives.
    • Trier les valeurs.

    "14", dans ton exemple, est une valeur qui pourrait être exclue dès le début.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Rédacteur/Modérateur

    Avatar de Jean-Philippe André
    Homme Profil pro
    Developpeur VBA, C# et VB.Net =]
    Inscrit en
    juillet 2007
    Messages
    14 127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Developpeur VBA, C# et VB.Net =]
    Secteur : Finance

    Informations forums :
    Inscription : juillet 2007
    Messages : 14 127
    Points : 32 252
    Points
    32 252
    Par défaut
    Salut,

    Pardon, je n'interviens jamais dans cette partie du forum, je manque de rigueur dune part, et du vocabulaire adéquat d'autre part

    L'approche actuelle est de construire mon sous-ensemble et de faire les combinaisons de n valeurs parmi N disponible, et dès que je tombe sur abs(somme)<=0.001 je considère avoir trouvé une combinaison, et j'exclus les valeurs de mon sous ensemble et je reprends au meme nombre de valeurs sur le sous en semble restant.

    J'ai pu optimisé l'approche en calculant la somme du complément, c'est à dire si j'ai 10 valeurs, lorsque je teste les combinaisons de 2, j'en profite pour faire les 8 qui restent en faisant le test Somme des n valeurs = Somme Total du sous-ensemble...

    Oui, de plus, j'ai pu trouvé un moyen d'écrêter les valeurs extremes qui seraient au dela de la somme des valeurs de signe opposé (cas de 14>abs(-2-8)).

    Le nombre max de 150 me gêne également, mais l'algo trouve assez vite pour 30 valeurs par exemple, mais à 50 valeurs ca mouline de trop.

    N'étant pas dans le forum Python, puis-je/dois-je te donner mon code actuel ?
    Cycle de vie d'un bon programme :
    1/ ca fonctionne 2/ ca s'optimise 3/ ca se refactorise

    Pas de question technique par MP, je ne réponds pas

    Apprendre à programmer avec Access 2016 et Access 2019

    Pensez à consulter la FAQ Excel et la FAQ Access

    Derniers tutos
    Excel et les paramètres régionaux
    Les fichiers Excel binaires : xlsb,

    Autres tutos

  4. #4
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 180
    Points
    180
    Par défaut
    Bonjour,
    ton problème fait partie des problèmes subset sum (en général NP difficiles). Pour une plage de valeur pas trop large, tu pourrais essayer un des algo en programmation dynamique (cherche zero sum subset dynamic programming) ; il y a pas mal de littérature sur ça.

  5. #5
    Rédacteur/Modérateur

    Avatar de Jean-Philippe André
    Homme Profil pro
    Developpeur VBA, C# et VB.Net =]
    Inscrit en
    juillet 2007
    Messages
    14 127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Developpeur VBA, C# et VB.Net =]
    Secteur : Finance

    Informations forums :
    Inscription : juillet 2007
    Messages : 14 127
    Points : 32 252
    Points
    32 252
    Par défaut
    Salut,

    merci, je vais me renseigner dans cette direction !
    Cycle de vie d'un bon programme :
    1/ ca fonctionne 2/ ca s'optimise 3/ ca se refactorise

    Pas de question technique par MP, je ne réponds pas

    Apprendre à programmer avec Access 2016 et Access 2019

    Pensez à consulter la FAQ Excel et la FAQ Access

    Derniers tutos
    Excel et les paramètres régionaux
    Les fichiers Excel binaires : xlsb,

    Autres tutos

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 104
    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 : 3 104
    Points : 7 097
    Points
    7 097
    Par défaut
    Peux-tu donner 2 ou 3 jeux de données exemple, pour orienter l'aide.

    3 exemples :
    série 1 :-718 -682 -665 -641 -594 -563 -518 -504 -486 -483 -468 -461 -432 -429 -385 -375 -348 -347 -342 -326 -322 -316 -310 -309 -296 -289 -287 -278 -268
    -260 -255 -241 -229 -218 -216 -199 -198 -187 -171 -157 -157 -153 -147 -145 -144 -125 -124 -111 -108 -99 -94 -81 -79 -78 -75 -68 -57 -52 -42
    -39 -36 -35 -34 -33 -25 -22 -11 5 17 28 36 49 54 56 59 60 63 64 66 66 68 69 77 78 78 79 81 84 88
    94 99 114 116 117 120 120 121 126 131 131 134 144 147 153 154 157 161 161 170 173 182 195 196 200 208 212 212 213 220
    247 262 262 271 274 276 279 287 290 307 307 309 346 406 428 430 451 478 496 496 514 527 534 550 551 556 602 615 625 683

    série 2 :
    -749 -722 -711 -689 -684 -662 -655 -654 -649 -647 -636 -635 -597 -571 -567 -551 -549 -542 -535 -520 -516 -504 -495 -494 -493 -490 -462 -433 -433
    -432 -420 -413 -396 -392 -379 -378 -377 -360 -351 -349 -311 -292 -291 -287 -286 -241 -237 -228 -225 -207 -195 -185 -176 -169 -165 -151 -145 -119 -115
    -107 -105 -91 -80 -80 -72 -69 -42 -39 -33 -31 -30 -21 -20 -16 -14 -5 1 14 30 48 55 72 100 114 135 141 195 221 221
    225 227 241 249 253 255 258 271 286 306 308 314 317 328 334 336 337 340 347 358 360 390 402 409 410 444 455 458 459 463
    465 474 490 497 511 530 538 542 557 562 575 576 582 601 602 605 608 616 657 658 674 683 696 697 697 707 709 718 729 737


    série 3 :
    -4891 -4812 -4804 -4732 -4553 -4511 -4486 -4341 -4314 -4301 -4229 -4156 -4099 -4087 -4035 -3996 -3855 -3768 -3678 -3504 -3291 -3179 -3074 -2998 -2939 -2704 -2658 -2593 -2585
    -2404 -2403 -2350 -2319 -2277 -2206 -2162 -2084 -1698 -1672 -1318 -1304 -1290 -1256 -1230 -1178 -1103 -1099 -1094 -1041 -1026 -904 -795 -739 -675 -649 -529 -426 -426 -398
    -394 -306 -268 -176 -116 -68 -54 9 40 101 149 190 208 372 439 584 593 621 678 706 749 820 863 1009 1044 1269 1362 1574 1608 1652
    1703 1722 1764 1810 2029 2209 2230 2235 2240 2266 2304 2362 2394 2413 2424 2434 2475 2517 2518 2572 2735 2786 2937 3189 3278 3402 3443 3571 3619 3689
    3710 3852 3900 3943 3957 4025 4103 4109 4124 4247 4272 4331 4367 4475 4479 4528 4534 4553 4560 4574 4585 4638 4646 4696 4699 4768 4885 4947 4949 4968
    ---
    Dans la série 1, j'ai une distribution qui suit une loi normale, donc une forte concentration autour de 0.
    Dans la série 2, j'ai des valeurs un peu plus dispersées.
    Et dans la série 3, j'ai des valeurs beaucoup plus dispersées.

    Dans la série 1, on est tenté de chercher des triplets(a,b,c) ... on va en trouver, et on va réduire le problème assez vite à un problème avec beaucoup moins de variables.
    Puis on cherche des quadruplets, des quintuplets ... c'est de plus en plus complexe, mais sur des volumes de plus en plus petits.
    Dans la série 2, ça devrait marcher aussi.
    Dans la série 3, c'est une autre histoire !
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2012
    Messages : 525
    Points : 259
    Points
    259
    Par défaut
    en python avec des générateurs : https://www.onlinegdb.com/rJgMJhyf1u

    fait à la va vite, y'a peut être des erreurs

  8. #8
    Rédacteur/Modérateur

    Avatar de Jean-Philippe André
    Homme Profil pro
    Developpeur VBA, C# et VB.Net =]
    Inscrit en
    juillet 2007
    Messages
    14 127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Developpeur VBA, C# et VB.Net =]
    Secteur : Finance

    Informations forums :
    Inscription : juillet 2007
    Messages : 14 127
    Points : 32 252
    Points
    32 252
    Par défaut
    Bonjour,

    voici des exemples de valeurs :
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    start=[-0.53,-0.63,-0.53,-2.76,-0.7,3.98,13.11,-60.6,-70.20,-56.07,360.7,-54.3,-48.54,-36.15,-58.17,-370.70,4.44,18.02,9.75,-192.15,-980.64,-418.80,-370.27,-355.24,-271.20,-181.78,-645.48,-1659.24,-1282.68,-602.40,-558.15,-286.20,-264.00,12.34,621.78,-790.92,-1137.96,0.01,0.02]
    start=[-4369.78,-1947.38,-1688.12,-1026.78,-1019.16,-945.00,-760.32,-653.64,-630.63,-620.61,-544.48,-272.24,123.32,123.32,122.4,118.58,106.98,101.71,97.38,87.72,86.50,86.43,84.85,81.69,75.07,72.2,71.81,69.56,69.09,63.1,61.47,59.54,53.48,52.7,48.96,33.98,29.5,20.02,18.45,17.72,16.06,14.94,9.22,8.30,4.98,4.74,3.32,3.32,3.16,1.66,1.66,1.66,1.58,1.58,-1.57]

    mon lot 2 d'exemples correspond à une des idées que j'ai essayées de mon côté : tri par valeur absolue décroissante, mais ca a tendance à ralentir les temps de traitement.

    Si je me fie à tes 3 cas, je pencherai pour le cas 3, dans la mesure où il est question de lettrage comptable en bout de compte

    Voici le code récursif adapté actuel en python, avec plusieurs jeux de valeurs exemple
    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
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    import datetime
    import sys
    n=5 # on initialise le nombre total de valeurs à ajouter à la liste de départ
    #start=[-1.57,-1026.78,1.58,84.85,52.7,33.98,-620.61,123.32,20.02,106.98,118.58,29.5,59.54,87.72,53.48,123.32,69.56,1.58,9.22,3.16,72.2,4.74,101.71,81.69,18.45,86.43,63.1,4.98,97.38,3.32,122.4,16.06,17.72,69.09,3.32,14.94,-4369.78,1.66,-653.64,75.07,8.30,86.50,-1688.12,-1947.38,-760.32,-630.63,-1019.16,-945.00,1.66,61.47,-272.24,-544.48,1.66,48.96,71.81]
    #start=[-14130.3,-9089.51,7850.25,7849.97,6280.09,1239.5,-8704.62,5469.92,2934.7,-158.1,422.26,19.5,16.34]
    #start=[-4369.78,-1947.38,-1688.12,-1026.78,-1019.16,-945.00,-760.32,-653.64,-630.63,-620.61,-544.48,-272.24,123.32,123.32,122.4,118.58,106.98,101.71,97.38,87.72,86.50,86.43,84.85,81.69,75.07,72.2,71.81,69.56,69.09,63.1,61.47,59.54,53.48,52.7,48.96,33.98,29.5,20.02,18.45,17.72,16.06,14.94,9.22,8.30,4.98,4.74,3.32,3.32,3.16,1.66,1.66,1.66,1.58,1.58,-1.57]
    #start=[-27255.90,4.58,27531.21,-0.05,-11061.87,-21.23,21.05,0.01,0.01,0.10,3360.13,-34.09,-9741.37,9738.76,-97.39,0.34,-0.18,0.14,-164.90,-325.55,43.59,-2149.28,2418.04,-24158.06,4643.46,-4635.20,0.01,-18.16,-8.26,-8.58]
    #start=[2,3,-1,-9,10]
    #values=[]
     
    start=[-0.53,-0.63,-0.53,-2.76,-0.7,3.98,13.11,-60.6,-70.20,-56.07,360.7,-54.3,-48.54,-36.15,-58.17,-370.70,4.44,18.02,9.75,-192.15,-980.64,-418.80,-370.27,-355.24,-271.20,-181.78,-645.48,-1659.24,-1282.68,-602.40,-558.15,-286.20,-264.00,12.34,621.78,-790.92,-1137.96,0.01,0.02]
    values=[]
    #values=[27531.21,-27255.90,-24158.06,-11061.87,-9741.37,9738.76,4643.46,-4635.20,3360.13,2418.04,-2149.28,-325.55,-164.90,-97.39,43.59,-34.09,-21.23,21.05,-18.16,-8.58,-8.26,4.58,0.34,-0.18,0.14,0.10,-0.05,0.01,0.01,0.01]
    #values=[-13321.27,8284.29,-5555.35,-5267.36,-4416.41,3952.43,3842.20,3520.36,3313.78,2918.83,2854.78,2763.20,2434.22,-2304.61,2210.5,2179.35,2070.25,1952.75,1902.88,-1597.39,1523.51,1487.83,1476.78,1436.60,1385.37,1347.80,1346.00,-1244.88,1240.98,1185.40,1097.74,1088.78,1085.92,-1062.07,975.48,-975,888.52,-792.57,732.00,720.26,-720.00,-720.00,-714.96,703.78,694.06,686.52,-679.77,656.12,647.68,600.03,576.63,568.11,533.85,-489.60,481.47,476.37,466.40,444.99,444.45,378.91,364.08,358.89,345.44,337.84,319.36,-302.40,297.6,297.57,288.82,285.38,266.21,242.66,224.79,218.38,183.71,162.62,158.3,158.09,155.95,147.98,127.73,109.90,105.85,-98.47,88.13,82.69,82.69,-78.02,73.78,70.19,69.09,56.39,56.14,51.12,51.12,44.80,-42.30,41.11,40.58,40.58,36.36,36.2,31.62,30.27,-28.38,22.13,20.03,19.58,17.39,17.39,17.39,16.34,15.78,15.23,14.23,14.23,-12.90,8.96,8.96,6.85,6.64,6.32,6.32,4.74,4.59,3.32,3.16,1.66,0.02]
    results=[] # liste des résultats
    index_utilises=[]
    indices=[]
    index_exclus=[]
    SommeDesValeurs=0
    Arret=True
    Compteur=0
    Codes=[]
    iDepart=2
    def combinaisons(n, p , i , k, s, c): # fonction récursive pour générer tous les groupes de p valeurs prises parmi n valeurs de l'ensemble
            global Arret
            if c_Valide(c):
                    if (i < p):
                            if ((k + (p - i)) <= n):
                                    for j in range(k + 1, n+1):
                                            #print("A")
                                            if Arret==True:
                                                    break
                                            if not indices[j-1] in index_utilises:
                                                    # appel récursif vers prochaine valeur du groupe                
                                                    combinaisons(n, p, i + 1, j, s + values[j-1], c + str(j-1) + ',') # ajout de la valeur dans la somme s et dans le groupe c
     
                    else:
                            if abs(s) <= 1e-03: # si la somme des valeurs du groupe vaut 0
                                print("B")
                                #results.append(c[0:len(c)-1]) # on ajoute un groupe de valeurs dans la liste results (exemple: (-1,2,1,2))
                                Trouve(c)
                            elif abs(s-SommeDesValeurs)<=1e-03:
                                print("C")
                                TrouveComplement(c)
     
     
    #for i in range(-n,n,2): # on génère les valeurs de l'ensemble dans la liste values
            #if i!=0:
                    #values.append(i) # ajoute une valeur dans la liste values
     
    def Trouve(c):
            global Arret
            print(c[0:len(c)-1])
            o=c[0:len(c)-1].split(',')
            for a in map(lambda x:int(x),o):
                index_utilises.append(indices[a])
                Codes.append(tuple((indices[a],Compteur)))
            print(len(values)-len(index_utilises))
            print(Codes)
            Arret=True
     
    def TrouveComplement(c):
            global Arret
            o=c[0:len(c)-1].split(',')
            x = map(lambda x: int(x),o)
            for i in range(len(start)):
                    if not i in index_exclus and not i in index_utilises and not i in x:
                            index_utilises.append(i)
                            Codes.append(tuple((i,Compteur)))
            print(len(values)-len(index_utilises))
            print(Codes)
            Arret=True
     
    def InitDeTout():
            try:
                    global Arret
                    global Compteur
                    global SommeDesValeurs
                    Compteur+=1
                    Arret = False
                    global n
                    values.clear()
                    indices.clear()
                    Exclure_Hors_Limite()
                    for i in range(len(start)):
                            if not i in index_utilises and not i in index_exclus :#and len(values)<30:
                                values.append(start[i])
                                indices.append(i)
                    print(indices)
                    n=len(values) # on évalue à nouveau le nombre total de valeurs contenues dans la liste de départ pour être sûr
                    SommeDesValeurs=sum(values)
            except:
                    print(sys.exc_info())
                    x=input()
    def A_Exclure(c):
            a=SommeNeg()
            b=SommePos()
            r=(c>0 and c+a>0) or (c<0 and c+b<0)
            #print(f"Test {c}:{r} , {a} et {b}")
            return r
     
    def Exclure_Hors_Limite():                
            for i in range(len(start)):
                    if not i in index_exclus and not i in index_utilises:
                        if A_Exclure(start[i])==True:
                            index_exclus.append(i)
     
    def SommePos():
            r=0
            for i in range(len(start)):
                    if not i in index_utilises and not i in index_exclus:
                            if start[i]>0:
                                r+=start[i]
            return r
     
    def SommeNeg():
        r=0
        for i in range(len(start)):
            if not i in index_utilises and not i in index_exclus:
                if start[i]<0:
                    r+=start[i]
        return r
     
    def c_Valide(c):
            if c=="":
                    return True
            #print(f"on teste {c}")
            o=c[0:len(c)-1].split(',')
     
            for a in o:
                    #print("c")
                    if indices[int(a)-1] in index_utilises:
                            return False
            return True
     
    print (SommeNeg())        
    print (SommePos())        
    print(A_Exclure(start[0]))
    while Arret==True:
            try:
                    InitDeTout()
                    print(values)
                    print(n)
                    print (f'début {Compteur}')
                    print(datetime.datetime.now())
            except:
                    print(sys.exc_info())
                    x=input()
            try:
                    for i in range(2,int((n+1)/2)+1): #for i in range(2,n+1): # gènère toutes les combinaisons : de combin(n,2) jusqu'à combin(n,n)
                            print(f"recherche des combinaisons de {i} composants")
                            if Arret==True:
                                    iDepart=i
                                    break
                            else:
                                    #print("ICI")
                                    combinaisons(n, i, 0, 0, 0, '') # appel de la fonction récursive pour générer les groupes de i valeurs prises dans n 
            except:
                    print(sys.exc_info())
                    x=input()
            print("fin")
            print(datetime.datetime.now())
            #for r in results:  # affiche toutes les combinaisons de combin(n,2) jusqu'à combin(n,n)
            #        print(r)
     
            print("index utilisés")
            print(index_utilises)
    print("solution")
    print("index utilisés")
    print(index_utilises)
    print(Codes)
    x=input()

    A 30 valeurs le temps est totalement OK, mais quand on passe à 40 puis 50+, ca mouline...

    Parmi les choses qui m'ont été proposées par ailleurs, un code sans récursivité, 4 h de traitement (on pourra envisager des traitements de nuit de toute facon)
    Cycle de vie d'un bon programme :
    1/ ca fonctionne 2/ ca s'optimise 3/ ca se refactorise

    Pas de question technique par MP, je ne réponds pas

    Apprendre à programmer avec Access 2016 et Access 2019

    Pensez à consulter la FAQ Excel et la FAQ Access

    Derniers tutos
    Excel et les paramètres régionaux
    Les fichiers Excel binaires : xlsb,

    Autres tutos

  9. #9
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    347
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 347
    Points : 1 213
    Points
    1 213
    Par défaut Des chiffres et des letres
    Bonjour,

    Même si le lettrage n'est pas univoque, il ne semble pas complètement libre. A priori le paiement suit la facture. Il semble donc possible d'exclure les associations entre paiement et facture (positif et négatif) si le premier est antérieur au second.

    J'aurais tendance à travailler à l'envers en constatant que la somme de tous les groupes à somme nulle forme un groupe à somme nulle.

    Ainsi je commencerai par calculer une somme brutale.

    Si le total S est 0, circulez il n'y a rien à voir. Je n'ai pas un lettrage fin mais l'équilibre est là.

    Si le montant de S est négatif (hypothèse que < 0 signifie sommes attendues), il y a une ou plusieurs factures qui ne sont pas couvertes. Je cherche la ou les factures qui, associées, correspondraient à cette somme en commençant par les plus récentes. Ce qui reste est alors le lettrage. Si je ne trouve pas (par exemple parce qu'il y a eu des paiements partiels) je retire les factures qui, associées, sont les plus proches en excès (en valeur absolue) à la somme (également en valeur absolue). J'ai donc une nouvelle somme S2 positive.

    Si le montant S est positif, c'est noël, le client a payé plus qu'il ne doit. Je retire les derniers paiements (c'est un choix qui suppose que le client a payé sur devis avant l'émission de la facture) jusqu'à obtenir une somme négative ou nulle.

    L'approche séquentielle n'est certainement pas parfaite mais elle devrait donner des résultats intéressants dans la plupart des cas.

    Le fait de travailler sur le complémentaire de la somme des groupe à somme nulle semble plus porteur que de constituer des pairs puis des trios puis... Par ailleurs, il peut absorber des paiements fractionnés ( 10 facture payées en 7 versement égaux par exemle) sans poser de problème.

    Ce ne sont que quelques pistes.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  10. #10
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 104
    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 : 3 104
    Points : 7 097
    Points
    7 097
    Par défaut
    Les nombres sont 'disparates' ... si on convertit en centimes pour travailler avec des entiers, l'amplitude est très grande comparée au nombre de lignes, donc la piste de chercher des paires, puis des triplets, puis des quadruplets ... ça ne donnera rien.
    Comme Guesset, je pensais à calculer la somme de tous les nombres, puis à chercher une liste de valeurs qui donne ce montant. Ainsi, on sait que tout le reste donne 0. Disons que avec cette optique, on cherche les 20 ou 30 qu'on va exclure, plutôt que les 120 ou 130 qui donnent une somme nulle. Ca peut engendrer un gros bénéfice. Mais pas forcément.

    La chronologie, utiliser le fait qu'un paiement arrive en principe après la facture correspondante. Oui, très probablement une bonne piste.

    Le langage utilisé : Python.
    Attention, Python peut être très efficace quand on l'utilise bien, mais basiquement, c'est lent ( c'est de l'interprété et pas du compilé).
    En gros, la philosophie que je me suis faite, c'est que Python est très bien si on arrive à écrire son programme sans la moindre boucle, c'est à dire si on utilise essentiellement des instructions du type : Tableau1 = f(Tableau2) où f est une fonction native. Donc le code Python que tu proposes, il sera très lent. La même chose en C sera BEAUCOUP plus rapide.

    Mais je ne suis pas du tout un pro de Python, c'est juste mon feeling.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  11. #11
    Rédacteur/Modérateur

    Avatar de Jean-Philippe André
    Homme Profil pro
    Developpeur VBA, C# et VB.Net =]
    Inscrit en
    juillet 2007
    Messages
    14 127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Developpeur VBA, C# et VB.Net =]
    Secteur : Finance

    Informations forums :
    Inscription : juillet 2007
    Messages : 14 127
    Points : 32 252
    Points
    32 252
    Par défaut
    J'aime beaucoup ton idée pour l'ordre des valeurs positives vs négatives, mais ca sortirait d'un cas général, avec contre exemple par nos amis comptables

    Lorsque tu évoques
    Le fait de travailler sur le complémentaire de la somme des groupe à somme nulle semble plus porteur que de constituer des pairs puis des trios puis
    tu fais une recherche de telle sorte que si tu as un groupe dont la somme vaut 123.45, tu cherches si la valeur -123.45 est disponible dans la liste ?
    Cycle de vie d'un bon programme :
    1/ ca fonctionne 2/ ca s'optimise 3/ ca se refactorise

    Pas de question technique par MP, je ne réponds pas

    Apprendre à programmer avec Access 2016 et Access 2019

    Pensez à consulter la FAQ Excel et la FAQ Access

    Derniers tutos
    Excel et les paramètres régionaux
    Les fichiers Excel binaires : xlsb,

    Autres tutos

  12. #12
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    347
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 347
    Points : 1 213
    Points
    1 213
    Par défaut Sous et soucis
    Bonsoir,
    Citation Envoyé par Jean-Philippe André Voir le message
    Tu fais une recherche de telle sorte que si tu as un groupe dont la somme vaut 123.45, tu cherches si la valeur -123.45 est disponible dans la liste ?
    Si la somme a une valeur qui existe dans la liste ou par combinaison d'éléments de la liste (normalement cette somme doit être relativement faible puisque c'est soit un reste à payer soit un trop perçu). A priori, il ne faudrait utiliser que des entrées de même signe.

    Cela revient à dire par exemple que s'il y a des impayés il doivent correspondre à une ou plusieurs factures. Dans ton exemple, si -123.45 représente la somme, je cherche la ou les factures qui présentent une somme de -123.45. Si je les trouve, toutes les autres sont mécaniquement couvertes par des paiements.

    Tes amis comptables supposent qu'on peut payer une facture avant de l'avoir reçu ? Ce doit être rare. Et je jure que ce ne sera pas de mon fait

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  13. #13
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 627
    Points : 11 564
    Points
    11 564
    Par défaut
    Citation Envoyé par Guesset Voir le message
    Tes amis comptables supposent qu'on peut payer une facture avant de l'avoir reçu ?
    Ben bien sûr. La facture n'est en rien une demande de paiement. C'est la transcription écrite d'un flux d'argent. La facture peut être émise avant, pendant ou après le paiement. C'est elle qui a une vraie valeur comptable et "juridique".
    • "Avant", c'est le cas que tu imagines, dans lequel le professionnel demande la juste rémunération de son travail passé.
    • "Pendant", c'est, par exemple, les courses au supermarché. Le ticket de caisse vaut facture. Et il y a sur ce petit document toutes les mentions légales nécessaires d'une facture.
    • "Après". Je suis sorti d'un magasin en ayant tout payé, et le commerçant m'a rattrapé en me disant "Attendez, Monsieur, votre facture !". Cela m'a perturbé puisque je venais de solder l'opération en payant tout. Mais la facture n'est pas une demande d'argent. C'est un papier officiel qui résume la transaction.

    Et souvent, les gens confondent les "avoirs" et les "remises". Les avoirs sont des anti-factures, ou des factures négatives. Ce n'est pas une ristourne sur un achat futur. C'est une facture annulée. On ne peut pas en distribuer à tous vents.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  14. #14
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    347
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 347
    Points : 1 213
    Points
    1 213
    Par défaut Fracture ou facture ?
    Bonjour Flodelarab,

    Sauf erreur de ma part mais dans les trois exemples cités, la facture est émise avant le paiement et je peux exiger de la voir, par exemple si je trouve le montant annoncé trop élevé. Le fait que je ne la vois pas ou que je l'oublie ne change rien à sa préexistence.

    Il me semble qu'en comptabilité il n'y a que des états comptables et que les flux ne sont que des changements d'états.

    Sur le plan juridique, c'est l'engagement sur devis ou contrat et/ou le service fait (accepté ou opposable) qui lie les deux parties. La facture ne garantit pas de droit à être payé. Si quelqu'un élague des arbres pendant l'absence et sans l'accord du propriétaire, il peut certes présenter une facture mais celle ci n'aura de valeur que s'il peut prouver un service fait opposable.

    La facture est effectivement un élément d'état comptable mais il ne résume pas la transaction. C'est le paiement (voire le non paiement partiel ou total en cas de contentieux) qui termine la transaction. Et ce flux génère un nouvel état comptable.

    On pourrait discuter des avances (à la signature) et des paiements à l'avancement (ces derniers faisant l'objet d'une facturation et de services faits) qui selon le cadre contractuel présentent des complexités réjouissantes.

    Mais ceci éloigne passablement du problème posé.

    Salut.
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  15. #15
    Membre averti Avatar de Galet
    Homme Profil pro
    Consultant/Programmeur Robotique industrielle
    Inscrit en
    mars 2010
    Messages
    170
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Consultant/Programmeur Robotique industrielle

    Informations forums :
    Inscription : mars 2010
    Messages : 170
    Points : 379
    Points
    379
    Par défaut
    Citation Envoyé par Guesset Voir le message
    Ainsi je commencerai par calculer une somme brutale.

    Si le total S est 0, circulez il n'y a rien à voir. Je n'ai pas un lettrage fin mais l'équilibre est là.

    Si le montant de S est négatif (hypothèse que < 0 signifie sommes attendues), il y a une ou plusieurs factures qui ne sont pas couvertes. Je cherche la ou les factures qui, associées, correspondraient à cette somme en commençant par les plus récentes. Ce qui reste est alors le lettrage. Si je ne trouve pas (par exemple parce qu'il y a eu des paiements partiels) je retire les factures qui, associées, sont les plus proches en excès (en valeur absolue) à la somme (également en valeur absolue). J'ai donc une nouvelle somme S2 positive.

    Si le montant S est positif, c'est noël, le client a payé plus qu'il ne doit. Je retire les derniers paiements (c'est un choix qui suppose que le client a payé sur devis avant l'émission de la facture) jusqu'à obtenir une somme négative ou nulle.
    Bonjour,
    La déduction S=0 => Pas de lettrage, suppose qu'une avance ne compense pas exactement un retard de règlement.
    Ne serait-il pas utile, dans ce cas, de calculer la valeur moyenne et l'écart type des valeurs pour s'assurer que cette probabilité est faible ?
    Windows 7 / Delphi Tokyo
    "Les choses ne changent pas. Change ta façon de les voir, cela suffit" Lao Tseu

  16. #16
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    347
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 347
    Points : 1 213
    Points
    1 213
    Par défaut Lettrage sans calligraphie
    Bonjour Galet,

    Citation Envoyé par Galet Voir le message
    La déduction S=0 => Pas de lettrage, suppose qu'une avance ne compense pas exactement un retard de règlement.
    Ne serait-il pas utile, dans ce cas, de calculer la valeur moyenne et l'écart type des valeurs pour s'assurer que cette probabilité est faible ?
    Je pense que tu as raison (sauf sur le terme avance qui a un sens contractuel très précis puisqu'il est du - sur demande - sans autre contrepartie que la signature du contrat) mais j'aurais tendance à le conditionner par un volume seuil de données pour éviter de prendre plus de temps à vérifier la probabilité qu'à faire le lettrage proprement dit.

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  17. #17
    Rédacteur/Modérateur

    Avatar de Jean-Philippe André
    Homme Profil pro
    Developpeur VBA, C# et VB.Net =]
    Inscrit en
    juillet 2007
    Messages
    14 127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Developpeur VBA, C# et VB.Net =]
    Secteur : Finance

    Informations forums :
    Inscription : juillet 2007
    Messages : 14 127
    Points : 32 252
    Points
    32 252
    Par défaut
    Bonjour,

    j'ai fini par m'arrêter sur un code en python qui a fait le travail, sans appel récursif, qui a apporté satisfaction

    Dites moi s'il est coutume de fournir le code dans ce forum algo, je le joindrais avec plaisir.

    Merci
    Cycle de vie d'un bon programme :
    1/ ca fonctionne 2/ ca s'optimise 3/ ca se refactorise

    Pas de question technique par MP, je ne réponds pas

    Apprendre à programmer avec Access 2016 et Access 2019

    Pensez à consulter la FAQ Excel et la FAQ Access

    Derniers tutos
    Excel et les paramètres régionaux
    Les fichiers Excel binaires : xlsb,

    Autres tutos

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

Discussions similaires

  1. Combinaison de nombres dont la somme est inférieure à une valeur
    Par senacle dans le forum Algorithmes et structures de données
    Réponses: 24
    Dernier message: 29/06/2018, 15h27
  2. Défi N°1 : Génération des ensembles de nombre dont la somme est identique
    Par millie dans le forum Défis langages fonctionnels
    Réponses: 143
    Dernier message: 08/02/2018, 19h45
  3. Réponses: 2
    Dernier message: 23/01/2014, 16h29
  4. [Vxi3] Afficher une valeur dont la date est max
    Par nannou86 dans le forum Deski
    Réponses: 1
    Dernier message: 27/08/2010, 15h47
  5. Rechercher les nombres dont la somme est donnée
    Par TMuet dans le forum Intelligence artificielle
    Réponses: 2
    Dernier message: 17/08/2009, 18h17

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