Macro de somme aléatoire pour resultat defini
Fermé
Bobchwitz
Messages postés
1
Date d'inscription
mercredi 17 mars 2021
Statut
Membre
Dernière intervention
17 mars 2021
-
17 mars 2021 à 09:24
eriiic Messages postés 24570 Date d'inscription mardi 11 septembre 2007 Statut Contributeur Dernière intervention 23 avril 2024 - 21 mars 2021 à 12:57
eriiic Messages postés 24570 Date d'inscription mardi 11 septembre 2007 Statut Contributeur Dernière intervention 23 avril 2024 - 21 mars 2021 à 12:57
A voir également:
- Macro de somme aléatoire pour resultat defini
- Somme si couleur - Guide
- Somme excel - Guide
- Macro word - Guide
- Macro logiciel - Télécharger - Organisation
- Telecharger macro convertir chiffre en lettre excel - Télécharger - Tableur
5 réponses
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
Modifié le 17 mars 2021 à 11:34
Modifié le 17 mars 2021 à 11:34
Bonjour,
Le soucis c'est qu'il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités.
Et 400 valeurs c'est colossal. C'est exponentiel et le nombre explose très vite...
Si tu en as, supprime déjà toutes les valeurs > à la somme à atteindre, ça sera toujours ça de gagné.
A moins d'un coup de chance il va te falloir un temps considérable. Et tu ne peux te permettre d'arrêter dès qu'une solution est trouvée (imaginons un coup de bol et que tu aies une solution de moins de 10 termes qui présentent encore un temps de calcul raisonnable, enfin pour 400 valeurs ça serait plutôt moins de 5-6 termes...). Pour que le résultat soit fiable il faut que tu sois sûr qu'il n'y a pas une 2nde possibilité et il faut laisser tourner...
Bon courage.
Par curiosité fait moi savoir si tu as trouvé et en combien de temps, ou au bout de combien de temps tu as laissé tomber ;-)
Tu peux mettre en pause ce programme pour mettre en veille le PC et relancer plus tard.
https://mon-partage.fr/f/6wHR2xmh/
eric
Le soucis c'est qu'il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités.
Et 400 valeurs c'est colossal. C'est exponentiel et le nombre explose très vite...
Si tu en as, supprime déjà toutes les valeurs > à la somme à atteindre, ça sera toujours ça de gagné.
A moins d'un coup de chance il va te falloir un temps considérable. Et tu ne peux te permettre d'arrêter dès qu'une solution est trouvée (imaginons un coup de bol et que tu aies une solution de moins de 10 termes qui présentent encore un temps de calcul raisonnable, enfin pour 400 valeurs ça serait plutôt moins de 5-6 termes...). Pour que le résultat soit fiable il faut que tu sois sûr qu'il n'y a pas une 2nde possibilité et il faut laisser tourner...
Bon courage.
Par curiosité fait moi savoir si tu as trouvé et en combien de temps, ou au bout de combien de temps tu as laissé tomber ;-)
Tu peux mettre en pause ce programme pour mettre en veille le PC et relancer plus tard.
https://mon-partage.fr/f/6wHR2xmh/
eric
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
18 mars 2021 à 18:31
18 mars 2021 à 18:31
bonjour,
Il existe une méthode très rapide pour réaliser cela.
termes de recherche: "programmation dynamique somme d'un sous ensemble"
Il y a de nombreux sites en français, pas toujours très abordables.
En anglais, voici un explication très claire, avec également des exemples de programmes:
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
Les programmes en exemple ne retournent pas la liste des solutions possibles, il faut légèrement les adapter pour récupérer cette liste.
Il existe une méthode très rapide pour réaliser cela.
termes de recherche: "programmation dynamique somme d'un sous ensemble"
Il y a de nombreux sites en français, pas toujours très abordables.
En anglais, voici un explication très claire, avec également des exemples de programmes:
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
Les programmes en exemple ne retournent pas la liste des solutions possibles, il faut légèrement les adapter pour récupérer cette liste.
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
18 mars 2021 à 19:05
18 mars 2021 à 19:05
ici, une méthode pour trouver toutes les sommes:
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
>
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
Modifié le 18 mars 2021 à 19:24
Modifié le 18 mars 2021 à 19:24
Bonjour,
attention quand même que le plus souvent trouver 1 somme valide n'est pas suffisant.
S'il s'agit d'attribuer des factures réglées par un paiement global, encore faut-il prouver que la solution trouvée est unique.
Sinon tu attribues le statut 'payé' à une mauvaise facture.
Et là ça devient très long s'il y a 400 valeurs. Récursivité ou pas, il faut tout explorer.
eric
attention quand même que le plus souvent trouver 1 somme valide n'est pas suffisant.
S'il s'agit d'attribuer des factures réglées par un paiement global, encore faut-il prouver que la solution trouvée est unique.
Sinon tu attribues le statut 'payé' à une mauvaise facture.
Et là ça devient très long s'il y a 400 valeurs. Récursivité ou pas, il faut tout explorer.
eric
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
>
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
18 mars 2021 à 19:22
18 mars 2021 à 19:22
cet algorithme retrouve toutes les combinaison donnant la sommes correcte.
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
>
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
Modifié le 18 mars 2021 à 19:29
Modifié le 18 mars 2021 à 19:29
Oui bien sûr, comme le mien. En vba ça serait mieux ici non ? ;-)
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
>
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
18 mars 2021 à 20:10
18 mars 2021 à 20:10
la première étape est de choisir un algorithme adapté.
regarde bien ce que fait l'algorithme, il évite totalement la complexité combinatoire, et est très rapide. ni colossal, ni exponentiel.
tout son intelligence consiste à faire le minimum de calculs utiles, parfaitement adapté au problème de sommes de nombres positifs.
la seconde étape est, en effet, de le programmer pour l'environnement cible.
une fois l'algorithme choisi, tout programmeur VBA peut le programmer.
regarde bien ce que fait l'algorithme, il évite totalement la complexité combinatoire, et est très rapide. ni colossal, ni exponentiel.
tout son intelligence consiste à faire le minimum de calculs utiles, parfaitement adapté au problème de sommes de nombres positifs.
la seconde étape est, en effet, de le programmer pour l'environnement cible.
une fois l'algorithme choisi, tout programmeur VBA peut le programmer.
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
Modifié le 20 mars 2021 à 18:08
Modifié le 20 mars 2021 à 18:08
Bonjour,
je n'ai pas vraiment pu tester correctement vu que tu ne traites pas les nombres décimaux.
Les factures ont des centimes...
J'ai quand même lancé sur 40 valeurs, et enlevant la valeur négative que tu ne traites pas non plus. En dehors du fait que tes solutions sont entières donc erronées, que tu en trouves 27 et moi 119, tu mets 15 s contre 12s pour moi.
Bon, tes debug.print doivent y être pour beaucoup.
Entendons nous bien. Pour moi une amélioration c'est un gain conséquent comme les 3 min annoncées contre des heures ou des jours voire des années de calcul.
Je sais que je perd 10% de temps pour afficher la progression pour voir si ça vaut le coup de continuer et de donner la possibilité de suspendre et reprendre, de pouvoir passer certaines limites.
C'est un choix voulu. Pas grave de mettre 33s au lieu de 30s si on augmente les possibilités sur les plus gros problèmes.
J'ai quand même préparé un autre jeu de 27 données entières.
Tu trouves 28 solutions en 38s.
Mon programme s'est arrêté automatiquement au bout de 18s. Il avait déjà 240 solutions, maxi que je lui impose. Déjà que 2 solutions c'est une de trop, inutile d'en sortir des centaines.
Donc pas trop probant pour l'instant...
En fait tu te bases sur quoi pour dire que ma proposition n'est pas terrible et qu'on peut faire beaucoup mieux ?
Du concret après analyse sérieuse de mon code et avoir bien approfondi le problème ou au feeling ?
eric
je n'ai pas vraiment pu tester correctement vu que tu ne traites pas les nombres décimaux.
Les factures ont des centimes...
J'ai quand même lancé sur 40 valeurs, et enlevant la valeur négative que tu ne traites pas non plus. En dehors du fait que tes solutions sont entières donc erronées, que tu en trouves 27 et moi 119, tu mets 15 s contre 12s pour moi.
Bon, tes debug.print doivent y être pour beaucoup.
Entendons nous bien. Pour moi une amélioration c'est un gain conséquent comme les 3 min annoncées contre des heures ou des jours voire des années de calcul.
Je sais que je perd 10% de temps pour afficher la progression pour voir si ça vaut le coup de continuer et de donner la possibilité de suspendre et reprendre, de pouvoir passer certaines limites.
C'est un choix voulu. Pas grave de mettre 33s au lieu de 30s si on augmente les possibilités sur les plus gros problèmes.
J'ai quand même préparé un autre jeu de 27 données entières.
Tu trouves 28 solutions en 38s.
Mon programme s'est arrêté automatiquement au bout de 18s. Il avait déjà 240 solutions, maxi que je lui impose. Déjà que 2 solutions c'est une de trop, inutile d'en sortir des centaines.
Donc pas trop probant pour l'instant...
En fait tu te bases sur quoi pour dire que ma proposition n'est pas terrible et qu'on peut faire beaucoup mieux ?
Du concret après analyse sérieuse de mon code et avoir bien approfondi le problème ou au feeling ?
eric
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
20 mars 2021 à 18:30
20 mars 2021 à 18:30
comme déjà écrit, il suffit de tout multiplier par 100 si il y a des centimes.
je propose un algorithme pour lequel 400 valeurs n'est pas du tout colossal, un algorithme dont le temps de travail n'est pas exponentiel.
par exemple, il met 28 secondes pour trouver toutes les combinaisons dont la somme fait 360020 parmi les 400 nombres de 90000 à 90399.
si tu le souhaites, je peux tester l'algorithme sur d'autres ensembles et d'autres sommes.
je propose un algorithme pour lequel 400 valeurs n'est pas du tout colossal, un algorithme dont le temps de travail n'est pas exponentiel.
par exemple, il met 28 secondes pour trouver toutes les combinaisons dont la somme fait 360020 parmi les 400 nombres de 90000 à 90399.
si tu le souhaites, je peux tester l'algorithme sur d'autres ensembles et d'autres sommes.
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
20 mars 2021 à 19:05
20 mars 2021 à 19:05
les 3 minutes annoncées pour 400 nombres et une somme de 1000000, c'était en python.
en VBA, 84 secondes pour découvrir qu'il n'y a pas de solution, 88 secondes dans le cas où il y a 1425 solutions, le temps de les afficher.
en VBA, 84 secondes pour découvrir qu'il n'y a pas de solution, 88 secondes dans le cas où il y a 1425 solutions, le temps de les afficher.
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
20 mars 2021 à 20:00
20 mars 2021 à 20:00
Teste avec ce jeu de données : https://mon-partage.fr/f/WoZQ8D2P/
(c'est version beta en cours mais qui devrait être correcte)
Je trouve 119 solutions en 13s
Si tu trouves toutes les solutions en moitié moins je suis preneur ;-)
(c'est version beta en cours mais qui devrait être correcte)
Je trouve 119 solutions en 13s
Si tu trouves toutes les solutions en moitié moins je suis preneur ;-)
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
Modifié le 20 mars 2021 à 20:21
Modifié le 20 mars 2021 à 20:21
c'est instantané, pas le temps de mesurer le temps écoulé, largement moins qu'une seconde:
+574+136+938+500
+1438+574+136
+710+938+500
+710+1438
+136+574+938+500
+136+1438+574
+381+810+136+821
+381+136+810+821
+374+200+136+938+500
+374+200+1438+136
+374+200+136+938+500
+374+200+136+1438
+515+810+2+821
+195+632+821+500
+195+381+632+2+938
+195+515+938+500
+195+515+1438
+328+200+136+710+138+136+500
+328+374+810+136+500
+328+374+136+810+500
+328+195+200+381+136+632+2+138+136
+328+195+515+200+136+138+136+500
+243+810+138+136+821
+243+136+810+138+821
+243+136+810+2+136+821
+243+381+574+810+2+138
+243+374+574+136+821
+243+374+710+821
+243+374+136+574+821
+243+374+200+381+810+2+138
+243+195+632+2+138+938
+243+195+136+136+938+500
+243+195+136+1438+136
+243+195+515+374+821
+307+374+381+810+2+138+136
+307+374+381+136+810+2+138
+307+195+200+810+136+500
+307+195+200+136+810+500
+307+195+374+632+2+138+500
+307+328+381+632+500
+307+243+515+200+381+2+500
+307+243+328+632+138+500
+307+243+328+632+2+136+500
+307+243+328+136+632+2+500
+307+243+328+515+374+381
+537+195+374+136+632+138+136
+537+328+515+632+136
+537+328+515+136+632
+537+328+195+374+574+2+138
+537+243+515+200+381+136+136
+537+307+328+200+2+138+136+500
+537+307+328+200+136+2+138+500
+600+200+574+138+136+500
+600+200+710+138+500
+600+200+710+2+136+500
+600+200+136+138+136+938
+600+200+136+574+138+500
+600+200+136+574+2+136+500
+600+200+136+710+2+500
+600+195+200+381+632+2+138
+600+195+200+381+136+136+500
+600+195+515+200+138+500
+600+195+515+200+2+136+500
+600+195+515+200+136+2+500
+600+328+136+810+138+136
+600+328+374+710+136
+600+328+374+136+574+136
+600+328+374+136+710
+600+328+195+515+374+136
+600+328+195+515+374+136
+600+243+195+200+136+138+136+500
+600+307+195+200+710+136
+600+307+195+200+136+574+136
+600+307+195+200+136+710
+600+537+243+632+136
+600+537+243+136+632
+600+537+307+328+374+2
+1028+136+710+138+136
+1028+195+515+136+138+136
+1028+537+200+381+2
+1028+537+243+200+2+138
+1028+537+307+2+138+136
+1028+537+307+136+2+138
+684+243+200+381+2+138+500
+684+243+328+374+381+138
+684+243+328+374+381+2+136
+684+243+328+374+381+136+2
+684+307+381+2+138+136+500
+684+307+381+136+2+138+500
+684+307+200+136+821
+684+307+200+136+821
+684+307+200+381+574+2
+684+307+328+195+632+2
+684+307+243+200+574+2+138
+684+307+243+195+200+381+138
+684+307+243+195+200+381+2+136
+684+307+243+195+200+381+136+2
+684+537+515+136+2+138+136
+1129+381+138+500
+1129+381+2+136+500
+1129+381+136+2+500
+1129+243+2+138+136+500
+1129+243+136+2+138+500
+1129+243+200+574+2
+1129+243+195+200+381
+1129+307+574+138
+1129+307+574+2+136
+1129+307+710+2
+1129+307+136+574+2
+1129+307+374+200+138
+1129+307+374+200+2+136
+1129+307+374+200+136+2
+1129+307+195+381+136
+1129+307+195+381+136
+1129+307+195+515+2
+1129+307+243+195+138+136
+1129+307+243+195+136+138
+1129+307+243+195+136+2+136
+1129+684+195+2+138
nombre de solutions: 119
27 2148
0 secs
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
20 mars 2021 à 23:37
20 mars 2021 à 23:37
Si tu peux tester avec ce jeu de 400 valeurs maintenant stp
En théorie, 54 solutions
https://www.cjoint.com/c/KCuwKhuB75D
En théorie, 54 solutions
https://www.cjoint.com/c/KCuwKhuB75D
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
Modifié le 21 mars 2021 à 09:18
Modifié le 21 mars 2021 à 09:18
instantané aussi, le temps de calcul est proportionnel à 400*2148.
*** 400 2148
+710+938+500
+710+1438
+374+710+632+432
+514+381+432+821
+194+574+810+432+138
+194+374+810+632+138
+427+514+133+574+500
+427+194+514+381+632
+243+381+133+432+138+821
+243+374+710+821
+243+514+432+138+821
+243+194+514+133+632+432
+243+427+194+710+574
+243+427+194+381+133+632+138
+243+427+194+514+632+138
+306+710+632+500
+306+514+374+133+821
+306+194+710+938
+306+427+194+514+133+574
+537+194+133+710+574
+537+194+514+133+632+138
+537+427+374+810
+600+306+810+432
+600+537+243+194+574
+682+374+133+138+821
+682+427+194+133+574+138
+682+243+591+632
+682+600+306+427+133
+133+374+133+432+138+938
+133+427+381+133+574+500
+133+427+514+574+500
+133+243+381+432+138+821
+133+243+194+381+133+632+432
+133+243+194+514+632+432
+133+243+427+133+574+138+500
+133+243+427+194+381+632+138
+133+306+133+138+938+500
+133+306+133+1438+138
+133+306+374+133+632+432+138
+133+306+374+381+133+821
+133+306+514+374+821
+133+306+427+194+381+133+574
+133+306+427+194+514+574
+133+306+243+374+133+138+821
+133+306+243+427+194+133+574+138
+133+537+194+710+574
+133+537+194+381+133+632+138
+133+537+194+514+632+138
+133+600+194+514+133+574
+133+682+374+138+821
+133+682+194+133+574+432
+133+682+194+374+133+632
+133+682+427+194+574+138
+133+682+600+306+427
nombre de solutions: 54
400 2148
0 secs
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
>
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
21 mars 2021 à 09:23
21 mars 2021 à 09:23
si la somme cible est 2148000, il lui faut 130 secondes pour déterminer qu'il n'y a pas de solution.
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
>
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
21 mars 2021 à 12:15
21 mars 2021 à 12:15
Bonjour,
j'avoue que je commence à être sidéré, je ne pensais pas ça possible.
il va me falloir pas mal de temps pour essayer de comprendre.
Bon, il y a bien des cas où il mettra des heures voire des jours, mais comme c'est ceux où il y a des millions de solutions ce qui pour moi n'a plus de sens dans le type de problème visé, ce n'est pas un pb. On arrête des 10-20 trouvées et c'est bon.
Par contre j'aimerais bien retrouver le jeu de données où tu trouvais 28 solutions et moi beaucoup plus.
Je pense que c'est suite à une erreur de ma part car je n'ai pas réussi à mettre en défaut ton algorithme, mais j'aimerais en avoir le coeur net.
En tout cas merci pour cette ouverture plus que prometteuse :-)
eric
j'avoue que je commence à être sidéré, je ne pensais pas ça possible.
il va me falloir pas mal de temps pour essayer de comprendre.
Bon, il y a bien des cas où il mettra des heures voire des jours, mais comme c'est ceux où il y a des millions de solutions ce qui pour moi n'a plus de sens dans le type de problème visé, ce n'est pas un pb. On arrête des 10-20 trouvées et c'est bon.
Par contre j'aimerais bien retrouver le jeu de données où tu trouvais 28 solutions et moi beaucoup plus.
Je pense que c'est suite à une erreur de ma part car je n'ai pas réussi à mettre en défaut ton algorithme, mais j'aimerais en avoir le coeur net.
En tout cas merci pour cette ouverture plus que prometteuse :-)
eric
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
1 476
>
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
21 mars 2021 à 12:30
21 mars 2021 à 12:30
c'est grâce à toi que j'ai découvert tout cela.
en lisant "il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités", je me suis demandé si c'était vraiment vrai.
et j'ai découvert la programmation dynamique.
donc, merci à toi!
en lisant "il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités", je me suis demandé si c'était vraiment vrai.
et j'ai découvert la programmation dynamique.
donc, merci à toi!
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
>
yg_be
Messages postés
22720
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
23 avril 2024
21 mars 2021 à 12:57
21 mars 2021 à 12:57
En tout cas il y a beaucoup à lire sur ce site.
Souvent d'un trop haut niveau pour moi mais ça reste super intéressant.
Souvent d'un trop haut niveau pour moi mais ça reste super intéressant.
18 mars 2021 à 15:41