Quelles sont les limites actuelles du Balanced Multi-Way Number Partitioning

Bonjour,

Aprés avoir intérrogé 7 "IA" populaires avec la question du même titre, la réponse commune est "qu'on sait pas vraiment".

Par exemple DeepSeek dit:

État actuel (2023) :

N (taille de l'ensemble de nombres) : Les algorithmes exacts peuvent gérer des ensembles de taille modérée (par exemple, N ≈ 50 à 100) en temps raisonnable, mais deviennent rapidement impraticables pour des N plus grands.

K (nombre de sous-ensembles) : Le nombre de sous-ensembles K influence également la complexité. Pour K = 2, le problème est plus simple, mais pour K > 2, la complexité augmente considérablement.

Suite à cela je finis de la part de DeepSeek avec le défi suivant:

Défi proposé:

N (taille de l'ensemble de nombres) : 500 nombres.
Plage des nombres : Chaque nombre est un entier aléatoire compris entre 1 et 10 000 000.
K (nombre de sous-ensembles) : 10 sous-ensembles.

Objectif : Partitionner ces 500 nombres en 10 sous-ensembles de taille égale (50 nombres par sous-ensemble) tout en minimisant la différence entre les sommes des éléments de chaque sous-ensemble.

DeepSeek dit que "Si un tel problème est résolu de manière efficace, cela constituerait un record notable dans le domaine de l'optimisation combinatoire." (Moi: d'autres IA ou personnes diront peut être autre chose, je ne sais pas à voir...)

La pertinence du défi a été validé par toutes les autres "IA", j'ai donc relevé mais surtout réussi le défi !

Pour ceux que ça intéresse, les résultats se trouvent: https://drive.google.com/drive/folde...8_?usp=sharing

Note 1: En plus d'être datée du 2025-02-08, la liste de nombres utilisée provient d'une source externe (voir fichier multiset.txt).
Note 2: Au regard des (autres) datas que je possède, l'interêt tiens plus de l'exercice que du défi.

Au lieu de me mettre des moins 1, feriez mieux de mettre un commentaire et de faire part de votre expertise ! Ttop facile d'arriver des cookies plein la bouche, de pouffer de rire, de mettre son petit moins 1 et de se barrer sans rien justifier ! Exprimez-vous !

Optimal_Balanced_Multi_Way_Number_Partitioning - 10 000 numbers - Range [1 - 1 000 000] - K_1_000 - (2 solutions): - date.2025-02-10
https://drive.google.com/drive/folde...U-?usp=sharing

Ce qu'en pense nos chères "IA" (en gros elles disent que le partitionnement ci-dessus n'est pas possible et que si ça l'était...):
Grok: https://x.com/i/grok/share/08oCP7RbSI8AoKc9HbF8ri9O2
ChatGPT: https://chatgpt.com/share/67ab54af-e...2-adfd524d974d
Gemini: https://g.co/gemini/share/0bac0c59663f
Qwen: https://chat.qwenlm.ai/s/662a877d-ef...5-3266774c1292

Et ici ça dit quoi ? Y'a un expert ?

Bonjour,
Je ne suis pas un expert du sujet, je vais rarement sur ce forum et je viens de découvrir votre discussion.
Je vous invite, puisque c'est une discussion, à présenter plus précisément votre démarche (au lieu de liens sur un site où l'on ne s'y retrouve pas forcément), c'est à dire votre logique de raisonnement, un algorithme, un pseudo code, un exemple de données, pour que l'on puisse rejouer tout ça voir ce que ça donne.
Cordialement.

@laurent_ott
(Vous dîtes ne pas être expert et venir rarement sur ce site alors que vous avez un paquet de publications pointues sur ce dît site. Je vais répondre à votre question même si celle ci semble vouloir me tester)

Ok en termes simples: Officiellement jusqu'à aujourd'hui, on sait pas partitionner efficacement toutes listes de nombres. On sait partitionner les petites mais pas les grandes.

Plus la liste est grande ou que les nombres sont grands, plus il est difficile, voire impossible, d'obtenir un partitionnement respectant les contraintes de somme et de taille pour chaque sous ensembles. Dés lors on utlise des algorithmes d'approximation.

A quoi ça sert ?
A gerer l'espace (disponible), le temps (imparti) et les forces (équilibre).

Dans la communauté scientifique ce genre de problème de partitionnement est majoritairement considéré pour les cas les plus difficiles, comme impossible à résoudre, sauf que si je m'en tiens à ce que disent les "IA", je viens de démontrer le contraire ou du moins en partie !

Les "IA" construisent leurs réponses en amalgamant toutes sortes de publications scientifiques. Elle sont théoriques mais je ne connais pas le gap entre la théorie et la pratique. D'oû la question de ce post "Quelles sont les limites..."

Un expert "honnête" pourra en dire plus. Un expert "honnête", oui, parce que certains préfèrent vous dénigrer (les petits -1 font partie de ce stratagème de dénigrement) ou pire vous insulter !

Pour toutes informations complémentaires je vous suggère d'intéroger une "IA"

- Les exemples de données sont déjà disponibles via les liens précédents https://drive.google..... Je vérrai plus tard pour des petites datas.
- Désolé je n'ai pas de code, ni de méthode à partager.

Citation:

---

Envoyé par mllm_so

On sait partitionner les petites mais pas les grandes.

---

Traduction : on ne peut pas. Si ça ne marche que pour de petits exemples, c'est que c'est inutilisable. Apparemment, tu n'as pas testé si ça marchait pour de petits exemples.

Citation:

---

Envoyé par mllm_so

Dés lors on utlise des algorithmes d'approximation.

---

Ou pas : vive les heuristiques, les approches très généralistes de type MIP ou CP ? Pour beaucoup de problèmes similaires, ça fait des miracles. Tout dépend de ce que tu cherches à faire (ce que tu ne dis pas).

Bonjour,

Si le but est de minimiser la différence entre les sommes d'ensembles de taille égale, la qualité d'un algorithme n'est pas tant de produire un résultat que de pouvoir prouver qu'il est le meilleur possible.

A défaut, ce ne sont que des assertions en l'air.

Par ailleurs, les résultats seuls sont faciles à pipoter :

• tirer au sort les valeurs,
• faire tourner un algorithme même médiocre pour faire la répartition
• reprendre certaines valeurs pour égaliser les sommes et présenter la liste ainsi modifiée comme les valeurs aléatoires originelles.

En résumé, sans l'algorithme et/ou la possibilité de tester avec des jeux de valeurs externes, il n'est pas possible de porter une appréciation réelle.


Salutations

@dourouc05

Citation:

---

Apparemment, tu n'as pas testé si ça marchait pour de petits exemples.

---

Houla, pas de conclusion hâtive. Cà fait déjà 4-5 ans que je balance mes datas sur le net et que j'ai tout de même pris le temps de tester tout type de taille. Vous inquietez pas...

Preuve 1 - Liste de 40 nombres - range [1 - 10000000] - partitionnée en K_3 sous-ensembles

Code:

---

1 2 3 4 5 6 7

Liste de nombres > https://www.random.org/integer-sets/?sets=1&num=40&min=1&max=10000000&seqnos=on&commas=on&order=index&format=html&rnd=date.2025-02-08   (2 x 60761817) + (1 x 60761816)   K_1: (12) 45765 + 1611807 + 2909105 + 4842418 + 5250271 + 5960852 + 6030429 + 6155905 + 6442989 + 6617885 + 6723637 + 8170753 = 60761816 K_2: (14) 652838 + 918717 + 977002 + 1012382 + 1087963 + 2056606 + 2967485 + 4413319 + 4863787 + 7638986 + 8346976 + 8379565 + 8469015 + 8977176 = 60761817 K_3: (14) 1629894 + 1731469 + 2525341 + 3116241 + 3427400 + 3633906 + 3969368 + 4528840 + 4566619 + 4804980 + 5772733 + 6355629 + 6814138 + 7885259 = 60761817

---

Preuve 2 - Liste de 50 nombres - range [1 - 10000000] - partitionnée en K_4 sous-ensembles

Code:

---

1 2 3 4 5 6 7 8

Liste de nombres > https://www.random.org/integer-sets/?sets=1&num=50&min=1&max=10000000&seqnos=on&commas=on&order=index&format=html&rnd=date.2025-02-08   (3 x 59282581) + (1 x 59282578)   K_1: (11) 1012382 + 2090314 + 2525341 + 4528840 + 4842418 + 6030429 + 6442989 + 6814138 + 7638986 + 8379565 + 8977176 = 59282578 K_2: (13) 45765 + 652838 + 918717 + 1275309 + 2967485 + 3427400 + 5768114 + 6155905 + 6355629 + 6617885 + 7718025 + 8170753 + 9208756 = 59282581 K_3: (13) 977002 + 1629894 + 3116241 + 3969368 + 4292558 + 4298284 + 4413319 + 4804980 + 4863787 + 5410859 + 5804756 + 6723637 + 8977896 = 59282581 K_4: (13) 1087963 + 1611807 + 1731469 + 2056606 + 2909105 + 3633906 + 4566619 + 5250271 + 5772733 + 5960852 + 7885259 + 8346976 + 8469015 = 59282581

---

@Guesset

Citation:

---

la qualité d'un algorithme n'est pas tant de produire un résultat que de pouvoir prouver qu'il est le meilleur possible.

---

Pas d'accord, parce que vu la complexité du problème je dirai que pour l'instant "l'important n'est pas le chemin mais l'arrivée".
Quand bien même un algo serait mal écrit, qu'il resterait le meilleur tant qu'il n'a pas de concurents. Enfin chacun voit comme il veut...

Citation:

---

Par ailleurs, les résultats seuls sont faciles à pipoter :
tirer au sort les valeurs,
faire tourner un algorithme même médiocre pour faire la répartition
reprendre certaines valeurs pour égaliser les sommes et présenter la liste ainsi modifiée comme les valeurs aléatoires originelles.

---

Pas concerné puisque les données que j'ai mis à dispositions proviennent justement d'une source externe (voir liens précédents https://drive.google.....). (Vous n'avez pas lu les précédents posts !)

Bonjour mllm_so,

Citation:

---

Envoyé par mllm_so

...Pas d'accord, parce que vu la complexité du problème je dirai que pour l'instant "l'important n'est pas le chemin mais l'arrivée".
Quand bien même un algo serait mal écrit, qu'il resterait le meilleur tant qu'il n'a pas de concurents. Enfin chacun voit comme il veut...

---

Un algorithme qui prétend résoudre un problème ne saurait se contenter d'offrir une solution meilleure que d'autres sans pouvoir garantir que c'est la meilleure. Les meilleures méthodes d'approximation, d'heuristique et autres techniques d'optimisations, peuvent donner de très bons résultats mais ne peuvent garantir que c'est l'optimal. Tant que cet algorithme probant n'existe pas, le problème reste non résolu. Il y a plein de problèmes comme cela pour lesquels n'existent que de bonne solutions sans garantie de l'optimal, ces problèmes (par exemple le voyageur de commerce) restent irrésolus.

Ce n'est pas un point de vue. C'est ce qui justifie la réponse de la communauté scientifique et, par extension, celle des IA. L'algorithme évoqué est peut-être très bon mais s'il ne peut prouver qu'il propose une solution optimale, il reste une approximation et non une solution.

Avoir une bonne approximation, c'est ok, mais cela ne relève pas le défi initial.

Salut

Citation:

---

Cà fait déjà 4-5 ans que je balance mes datas sur le net et que j'ai tout de même pris le temps de tester tout type de taille. Vous inquietez pas

---

Ah... et on aurait dû deviner ça ?

De manière plus générale, habituellement, sur ce forum, on a 2 types d'intervention :
1) très majoritaire, les personnes qui viennent demander de l'aide.
2) très minoritaires, les personnes qui ont trouvé une solution à un problème intéressant, et qui partagent leur travail.
Ces 2 types d'intervention sont bien reçus.

'je suis très fort, j'ai une certaine solution à un certain problème, mais je ne vous en dis pas trop'
Ce 3ème type d'intervention est forcément mal perçu.

@Guesset

Citation:

---

Avoir une bonne approximation, c'est ok, mais cela ne relève pas le défi initial.

---

Je suis bien d'accord avec vous mais je vois pas le rapport avec les résolutions que je viens de donner puisqu'elles sont optimales.

Est ce que mon algo à la prétention de tout résoudre ?
Non. D'ailleurs lorsque je le lance je n'ai même aucune certitude de trouver une solution. Jusqu'à présent j'ai résolu tout ce que je voulais. A partir de là on en pense ce qu'on veut.

@tbc92

Citation:

---

Ah... et on aurait dû deviner ça ?

---

Y'avait rien à deviner mais surtout rien à affirmer ! Mais bon ch'ui cool avec ça. Tous les avis sont les bienvenus.

Citation:

---

'je suis très fort, j'ai une certaine solution à un certain problème, mais je ne vous en dis pas trop'

---

Je pense pas que ça soit la bonne lecture à avoir. Vous mésestimez totalement la portée des résolutions que je viens de donner. Lorsqu'on la saisit on se doute bien que je peux pas partager mon code ! D'ailleurs quel prestigitateur dévoile ses tours ?

Sur ce je passe en résolu.

(mes datas via google/drive ne sont plus accessibles)

Citation:

---

Envoyé par mllm_so

D'ailleurs quel prestigitateur dévoile ses tours ?

---

C'est le principe des communautés et de la recherche. Si on ne dévoile rien de ses astuces, pourquoi venir en parler ici ou ailleurs ?

Si tu ne dévoiles rien de la méthode, pourquoi dévoiler même le résultat ? Peut-être as-tu laissé tourner deux ou trois supercalculateurs avec un algorithme simplissime pour trouver des résultats en explorant toutes les solutions exhaustivement. Certes, tu as une bonne chance d'avoir l'optimum, mais ça n'est pas une avancée pour autant. (Compare avec les solveurs de VRP de NVIDIA : ils ne communiquent pas sur les temps de calcul, il y a un loup.)

Sur un problème similaire, https://github.com/google/or-tools/b...r_heuristics.h (code d'un collègue) résout du set cover en taille énorme bien plus vite que les heuristiques existantes (dans les 15 000 fois plus rapide sur d'énormes instances, largement plus sur de petites).

Citation:

---

Envoyé par Guesset

Un algorithme qui prétend résoudre un problème ne saurait se contenter d'offrir une solution meilleure que d'autres sans pouvoir garantir que c'est la meilleure. Les meilleures méthodes d'approximation, d'heuristique et autres techniques d'optimisations, peuvent donner de très bons résultats mais ne peuvent garantir que c'est l'optimal. Tant que cet algorithme probant n'existe pas, le problème reste non résolu. Il y a plein de problèmes comme cela pour lesquels n'existent que de bonne solutions sans garantie de l'optimal, ces problèmes (par exemple le voyageur de commerce) restent irrésolus.

Ce n'est pas un point de vue. C'est ce qui justifie la réponse de la communauté scientifique et, par extension, celle des IA. L'algorithme évoqué est peut-être très bon mais s'il ne peut prouver qu'il propose une solution optimale, il reste une approximation et non une solution.

---

Sauf que tout le monde part d'une certaine conjecture (P vs. NP) : a priori, on ne devrait jamais trouver d'algorithme qui donne une solution optimale à tous les coups sur tous les problèmes. Chercher cet algo idéal reviendrait à prouver P = NP : beaucoup de gens s'y sont cassé les dents (et produit des résultats intéressants et utiles en chemin).

Il n'empêche qu'on peut considérer certains problèmes comme résolus : il n'y a plus beaucoup d'intérêt à continuer à chercher des solutions pour un TSP, on a des heuristiques pour résoudre dans des temps raisonnables tous les TSP qu'on peut vouloir résoudre en pratique, avec d'excellentes solutions (peut-être pas optimales).

Ce n'est pas un point de vue, c'est un fait reconnu par la communauté scientifique ;). (Point de vue recherche opérationnelle, pas algorithmique fondamentale.)

Bonjour dourouc,

Citation:

---

Envoyé par dourouc05

...Sauf que tout le monde part d'une certaine conjecture (P vs. NP) : a priori, on ne devrait jamais trouver d'algorithme qui donne une solution optimale à tous les coups sur tous les problèmes. Chercher cet algo idéal reviendrait à prouver P = NP : beaucoup de gens s'y sont cassé les dents (et produit des résultats intéressants et utiles en chemin).
Il n'empêche qu'on peut considérer certains problèmes comme résolus : il n'y a plus beaucoup d'intérêt à continuer à chercher des solutions pour un TSP, on a des heuristiques pour résoudre dans des temps raisonnables tous les TSP qu'on peut vouloir résoudre en pratique, avec d'excellentes solutions (peut-être pas optimales).
Ce n'est pas un point de vue, c'est un fait reconnu par la communauté scientifique ;). (Point de vue recherche opérationnelle, pas algorithmique fondamentale.)

---

Il y a effectivement deux domaines d'appréciation : théorique et pratique.

C'est ce que j'essayais de faire comprendre au PO. Une réponse opérationnelle ne garantissant pas l'optimal ne contredit pas la réponse IA sur l'axe théorique.

Un problème est résolu quand on sait trouver et prouver la solution optimale. La nature du problème n'y change rien. Avec un problème NP on sait déjà qu'il y a une solution optimale. Qu'elle ne soit pas atteignable dans un temps raisonnable est un aspect pratique qui amène à se contenter d'algorithmes plus rapides ne garantissant pas l'optimal.

Pratique : ces algorithmes peuvent être suffisamment opérationnels pour être utilisés. Théorique : ils ne sont pourtant pas une résolution du problème sinon P = NP. Or, jusqu'alors, P = NP n'est ni prouvé ni réfuté.

Remarque : un problème n'a pas besoin d'être NP pour nécessiter des approches non exhaustives.

Salut

Bonjour,

J’ai testé plusieurs approches pour développer un algorithme en VBA capable de retrouver le résultat du message 8 avec ses 50 nombres répartis en 4 groupes, et finalement j’ai opté sur un solveur (que j’avais écrit pour faire des rapprochements bancaires) qui cherche les solutions qui s’approchent au mieux de la moyenne. Ça ne marche pas à tous les coups mais ça peut trouver la solution en quelques secondes (voir la feuille « Test_1 » du fichier joint).

J’ai testé sur 1 000 nombres compris entre 1 et 10 000 répartis en 10 groupes de taille égale (feuille « Test_2 ») et ça semble marcher : j’ai 9 groupes dont la somme est égale à la moyenne, et le 10e a un écart de 7.

Comme avec 10 000 nombres compris entre 1 et 100 000 répartis en 10 groupes. C’est plus rapide quand la taille des groupes n’est pas obligatoirement égale (feuille « Test_3 »).

D’où ma question : quand les sommes de tous les groupes sauf un sont égales à la moyenne, et que l’écart entre la moyenne et la somme du dernier groupe et inférieure au nombre de groupes, peut-on considérer que le résultat est optimal ?

Le fichier Excel : Pièce jointe 664570


Cordialement.

Oui ou non, comme tu veux !

La fonction 'objectif' est celle que l'on se fixe. Si on a une somme de 100000004 et qu'on vise 10 groupes, on peut se fixer par exemple ces 2 objectifs (l'un OU l'autre, pas les 2 évidemment):
Objectif 1 : la moyenne (arrondie à l'entier le plus proche) est 10000000 ; on veut 9 groupes avec ce total et un groupe avec 10000004.
ou Objectif 2 : On veut 6 groupes avec 10000000 et 4 groupes avec 10000004.

Ici, clairement, l'objectif visé par le solveur était visiblement l'objectif 1.
Le problème a probablement été mal formulé, parce que dans ma lecture, la discussion visait plutôt l'objectif 2.

Il y a un '''souci''' avec ton expérience (1000 nombres entre 1 et 10000 à répartir en 10 groupes).
J'ai 1000 nombres, dont la somme est de l'ordre de 5 Millions, disons 5 Millions tout rond pour faciliter.
Je veux donc faire 10 groupes qui auront chacun une somme de 500000.

Le nombre de façons de choisir 100 nombres parmi 1000, c'est 10^139, c'est énorme. Et tous ces tirages vont donner des sommes qui varient entre 100 et 1 Million. On a une gaussienne, et si on enlève les totaux extrêmes, environ la moitié de tous ces 10^139 tirages vont donner un résultat entre 450000 et 550000...
Donc il y a vraiment plein d'ex-aequo, plein de tirages qui permettent d'atteindre n'importe quel total voulu, proche de ce 500000.
Il y a tellement de partitions qui donnent la bonne réponse, qu'en trouver une est facile.

Dès qu'on a trouvé une solution où les 10 sous-groupes ont le total voulu, c'est fini.

Si maintenant on prend 1000 nombres aléatoires, mais sur un intervalle BEAUCOUP plus grand (1000 nombres entre 1 et 10^30 par exemple).
Dans ce cas, peut-être que la meilleure combinaison est constituée de sous-groupes dont la somme est très proche de la moyenne, très proche mais pas égale.
Et donc, quand on a une solution qui paraît vraiment bonne, on n'est toujours pas certain qu'il n'y a pas mieux.
Et là, c'est une autre histoire.

On a toujours 1000 nombres à répartir en 10 groupes, mais le problème n'est plus du tout du même ordre.

Et dans l'expérience initiale (500 nombres de l'ordre de 5 Millions à répartir en 10 groupes), on a le même '''souci''', on a plein d'ex-aequo. Certes moins que dans ton expérience, mais quand même plusieurs milliers voire plusieurs millions de solutions qui donnent toutes le résultat visé.

Bonjour,

Vous avez raison de souligner ce biais.
On peut aussi raisonner par l'absurde : Soit un tirage idéalement aléatoire de 100 nombres compris entre 1 et 100 à répartir entre 10 groupes égaux.
Il suffit de classer ces nombres par ordre croissant, de prendre les 5 premiers et les 5 derniers pour avoir un groupe qui vaut 505, idem pour les groupes suivants.

Bonjour laurent_ott,

Citation:

---

Envoyé par laurent_ott

On peut aussi raisonner par l'absurde : Soit un tirage idéalement aléatoire de 100 nombres compris entre 0 et 100 à répartir entre 10 groupes égaux.
Il suffit de classer ces nombres par ordre croissant, de prendre les 5 premiers et les 5 derniers pour avoir un groupe qui vaut 505, idem pour les groupes suivants.

---

Je ne comprends pas comment on peut atteindre 505 (la probabilité d'avoir 5x1 et 5x100 est très très faible). En moyenne les 5 plus petits vaudront environ 10 et les 5 plus grands 490 (485 si 100 n'est pas l'une des valeurs - il y a 100 tirages mais 101 valeurs sinon). On obtient donc une moyenne de 500 (mais la valeur effective pourrait aller de 0 à 10000).

Ceci étant, le principe de les trier est le premier qui vienne à l'esprit. Ne serait-ce que pour faire tomber la complexité première en remarquant qu'un groupe des plus petites valeurs doit se terminer au moins à un indice donné pour ne pas être trop loin de la moyenne. Respectivement pour les plus grands.

Salut

Avec 10 nombres aléatoires entre 1 et 100, 505 est le résultat le plus fréquent.

Bonjour,
Dans ce tirage idéal, les nombres de 1 à 100 sont tirés une fois chacun, donc quand ils sont triés, les 5 premiers + les 5 derniers donne : 1+2+3+4+5+96+97+98+99+100 = 505
Pour le groupe suivant : 6+7+8+9+10+91+92+93+94+95=505.
Ainsi de suite.
Mais c'est absurde, évidement.

Bonjour tbc92,

Citation:

---

Envoyé par ;12070657

Avec 10 nombres aléatoires entre 1 et 100, 505 est le résultat le plus fréquent.

---

Ce qui me gênait était, d'une part, que les 100 tirages piochaient dans 101 valeurs de 0 à 100 et, d'autre part, qu'ils n'étaient pas indépendants (type loterie sans doublon).

Mais pour l'illustration cherchée, c'est OK.

Salut.

Liste de 50 nombres - range [1 - 100 000 000] - partitionnée en K_3 sous-ensembles - date.2025-02-19

Code:

---

1 2 3 4 5 6 7

Liste de nombres > https://www.random.org/integer-sets/?sets=1&num=50&min=1&max=100000000&seqnos=on&commas=on&sort=on&order=index&format=html&rnd=date.2025-02-19   (3 x 826169315)   K_1: (16) 560856 + 5911064 + 19493069 + 25666845 + 37494885 + 38021255 + 51989957 + 55022311 + 58396297 + 62221556 + 68200716 + 69279148 + 69675437 + 81891309 + 88194655 + 94149955 = 826169315 K_2: (17) 1027064 + 7411267 + 11102299 + 12097816 + 25580653 + 30389595 + 31126332 + 51972183 + 52508683 + 57875976 + 59962904 + 66996519 + 80571448 + 80638138 + 80974972 + 84394744 + 91538722 = 826169315 K_3: (17) 8754942 + 13542338 + 13619963 + 20815458 + 22659500 + 24028677 + 27677460 + 34389613 + 47487061 + 62750892 + 64004792 + 66206108 + 75120512 + 76915066 + 87116658 + 88559267 + 92521008 = 826169315

---

Moi aussi j'y arrive, exemples parmi d'autres :

---------------

(19) 560856, 1027064, 8754942, 19493069, 20815458, 22659500, 34389613, 37494885, 38021255, 47487061, 51972183, 51989957, 52508683, 55022311, 59962904, 66996519, 76915066, 88559267, 91538722
(17) 5911064, 7411267, 11102299, 12097816, 13542338, 25580653, 27677460, 31126332, 62750892, 64004792, 66206108, 68200716, 75120512, 80571448, 88194655, 92521008, 94149955
(14) 13619963, 24028677, 25666845, 30389595, 57875976, 58396297, 62221556, 69279148, 69675437, 80638138, 80974972, 81891309, 84394744, 87116658

---------------

(17) 12097816, 20815458, 25580653, 55022311, 64004792, 69279148, 75120512, 76915066, 80571448, 1027064, 7411267, 30389595, 34389613, 37494885, 51989957, 91538722, 92521008
(18) 560856, 5911064, 11102299, 13619963, 19493069, 38021255, 51972183, 52508683, 62750892, 66206108, 66996519, 69675437, 84394744, 88559267, 22659500, 25666845, 57875976, 88194655
(15) 58396297, 59962904, 62221556, 80638138, 80974972, 81891309, 94149955, 13542338, 24028677, 27677460, 87116658, 8754942, 31126332, 47487061, 68200716

---------------

(17) 5911064, 13542338, 19493069, 34389613, 38021255, 51972183, 75120512, 87116658, 92521008, 25580653, 27677460, 47487061, 58396297, 59962904, 62221556, 62750892, 64004792
(18) 24028677, 30389595, 52508683, 66206108, 68200716, 88194655, 88559267, 1027064, 12097816, 13619963, 20815458, 22659500, 31126332, 37494885, 51989957, 66996519, 69279148, 80974972
(15) 560856, 7411267, 8754942, 11102299, 25666845, 55022311, 57875976, 69675437, 76915066, 80571448, 80638138, 81891309, 84394744, 91538722, 94149955

---------------

Bref, il n'y a pas de quoi casser trois pattes à un canard.
Et je ne vois pas le rapport avec le "défi" du premier message où il faut ventiler 500 nombres compris entre 1 et 10 000 000 en dix groupes de même taille.

Et dans la question posée à ChatGPT, c'était encore un autre problème, on ne parlait pas de 10 groupes de 100, mais 100 groupes de 10. En combinatoire, on a 10^80 fois plus de cas à analyser si on fait une recherche exhaustive... toute petite différence.

@laurent_ott

Citation:

---

Moi aussi j'y arrive, exemples parmi d'autres

---

J'vous rassure j'en doutais pas, d'autres l'on fait bien avant nous et avec des nombres bien plus grands !

Cas de Subset Sum:
Pour le 2eme problème de cette page https://stackoverflow.com/questions/...for-large-sums, les réponses suivantes ont été apportées (je ne les ai pas revérifiées depuis)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

target : 262988806539946324131984661067039976436265064677212251086885351040000 subset : [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 29220978504438480459109406785226664048473896075245805676320594560000, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 10519552261597852965279386442681599057450602587088490043475414041600, 5367118500815231104734380838102856661964593156677801042589496960000, 3246775389382053384345489642802962672052655119471756186257843840000, 1826311156527405028694337924076666503029618504702862854770037160000, 335444906300951944045898802381428541372787072292362565161843560000, 214684740032609244189375233524114266478583726267112041703579878400, 202923461836378336521593102675185167003290944966984761641115240000] subset : [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 42078209046391411861117545770726396229802410348353960173901656166400, 21468474003260924418937523352411426647858372626711204170357987840000, 7305244626109620114777351696306666012118474018811451419080148640000, 4675356560710156873457505085636266247755823372039328908211295129600, 2629888065399463241319846610670399764362650646772122510868853510400, 1341779625203807776183595209525714165491148289169450260647374240000, 858738960130436976757500934096457065914334905068448166814319513600] subset : [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 42078209046391411861117545770726396229802410348353960173901656166400, 16436800408746645258249041316689998527266566542325765692930334440000, 10519552261597852965279386442681599057450602587088490043475414041600, 7305244626109620114777351696306666012118474018811451419080148640000, 1826311156527405028694337924076666503029618504702862854770037160000, 811693847345513346086372410700740668013163779867939046564460960000, 657472016349865810329961652667599941090662661693030627717213377600, 519484062301128541495278342848474027528424819115480989801255014400, 202923461836378336521593102675185167003290944966984761641115240000] subset : [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 29220978504438480459109406785226664048473896075245805676320594560000, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 7305244626109620114777351696306666012118474018811451419080148640000, 4675356560710156873457505085636266247755823372039328908211295129600, 3246775389382053384345489642802962672052655119471756186257843840000, 2629888065399463241319846610670399764362650646772122510868853510400, 1826311156527405028694337924076666503029618504702862854770037160000, 1168839140177539218364376271409066561938955843009832227052823782400, 657472016349865810329961652667599941090662661693030627717213377600, 202923461836378336521593102675185167003290944966984761641115240000] subset : [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 29220978504438480459109406785226664048473896075245805676320594560000, 21468474003260924418937523352411426647858372626711204170357987840000, 10519552261597852965279386442681599057450602587088490043475414041600, 7305244626109620114777351696306666012118474018811451419080148640000, 5367118500815231104734380838102856661964593156677801042589496960000, 2629888065399463241319846610670399764362650646772122510868853510400, 2385386000362324935437502594712380738650930291856800463373109760000, 1168839140177539218364376271409066561938955843009832227052823782400, 292209785044384804591094067852266640484738960752458056763205945600] subset : [116883914017753921836437627140906656193895584300983222705282378240000, 42078209046391411861117545770726396229802410348353960173901656166400, 29220978504438480459109406785226664048473896075245805676320594560000, 21468474003260924418937523352411426647858372626711204170357987840000, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 10519552261597852965279386442681599057450602587088490043475414041600, 5367118500815231104734380838102856661964593156677801042589496960000, 3246775389382053384345489642802962672052655119471756186257843840000, 1826311156527405028694337924076666503029618504702862854770037160000, 1341779625203807776183595209525714165491148289169450260647374240000, 858738960130436976757500934096457065914334905068448166814319513600, 335444906300951944045898802381428541372787072292362565161843560000, 214684740032609244189375233524114266478583726267112041703579878400, 202923461836378336521593102675185167003290944966984761641115240000] subset : [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 42078209046391411861117545770726396229802410348353960173901656166400, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 3246775389382053384345489642802962672052655119471756186257843840000, 2629888065399463241319846610670399764362650646772122510868853510400, 1826311156527405028694337924076666503029618504702862854770037160000, 657472016349865810329961652667599941090662661693030627717213377600, 292209785044384804591094067852266640484738960752458056763205945600, 202923461836378336521593102675185167003290944966984761641115240000] Auteur: maxtuno.github.io (Je ne sais pas pourquoi, mais cet auteur est identifié sur certains forums / posts, comme peu crédible, complotiste, ou je ne sais quoi d'autre, alors qu'il présente de bons résultats)

---

Dans mon cas si je m'en tiens (tenais) aux conclusions de chaque "IA" mes résultats (K_1_000) sont à minima révolutionnaires (allez voir les liens) ! D'oû mon questionnement "Quelles sont les limites ..." sachant que je peux partitionner, que ce soit pour le "Balanced Multi Way Number Partitioning" ou le "(Balanced) Bin Packing 1d" des listes bien plus grandes.

Théorie vs réalité:
Au regard des résultats que je présente (et revendique), y'a t'il un expert pour confirmer, infirmer les conclusions que donne les "IA" ?

Ok j'reviens à la charge. Après avoir requestionné les IA (Grok, ChatGPT, Gemini, Copilot, Qwen, Deepseek, Perpexity, Mistral..) qui ont toutes donné les mêmes réponses d'infaisabilité, je peux désormais affirmer que tout ce qu'elles disent est absolument faux ! Non pas à cause de mes algos et datas mais parce que après avoir pousser Deepseek dans ses retranchements il m'a pondu un code plutôt efficace. Est ce qu'il le tient de sa "réflexion", je ne sais pas (autodidacte, je ne suis pas au fait de tout ce qui existe). Il donne des résultats similaires à l'un des miens, et l'un ou l'autre se révèlent plus précis sur certains cas.
La différence c'est qu'il nécessite (toujours) plus de mémoire. Cas pour > N = 10000 / K = 1000 (sans contrainte de taille et environnement de dev non-optimal):
Algo deepseek > 300 mo + 1 sec alloué par sous ensemble > temps d'éxecution = 23 sec
Mon (2e) algo > 16 Mo + pas de limite de temps alloué > temps d'éxecution = 7 sec

Bref, quelques corrections pour l'un et l'autre algos pour en faire des outils parfaits (ou presque parfaits ?).

Pourquoi maintenir cette idée d'infaisabilité ?! Mystére...

Citation:

---

Envoyé par mllm_so

Pourquoi maintenir cette idée d'infaisabilité ?! Mystére...

---

Parce que, à moins d'un bouleversement profond de la théorie de l'informatique (P = NP), il n'existe pas d'algorithme en temps polynomial pour ce problème. C'est une notion très théorique et inattaquable par des expériences, uniquement par des preuves mathématiques.

Beaucoup de gens continuent de confondre la théorie et la pratique : on résout plein de problèmes NP-hard de très grande taille en pratique. On le fait parfois avec des algorithmes exacts dont le temps d'exécution est exponentiel en la taille du problème (plus rapides que des algos polynomiaux, selon les cas).

Une expérience plus intéressante sur tes algos : sont-ils exacts ? Existe-t-il une meilleure solution, avec un meilleur équilibre entre tes partitions ? Vu ce que tu dis ("plus précis sur certains cas"), je suppose que le résultat n'est pas toujours parfait.
Tu peux ensuite en calculer la complexité (théoriquement) et voir à quel point elle est corrélée avec tes expériences, tant pour le temps d'exécution que la mémoire.
Pour un algorithme non exact, à quel point est-il proche de la meilleure solution ? Parfois, tu peux prouver que tu seras toujours à un facteur 2 ou 1/n de l'optimum pour n nombres à partitionner (comme https://www.ijcai.org/Proceedings/11/Papers/122.pdf).

Précision: je suis autodidacte donc n'attendez pas de ma part un langage trop ou trés technique. Je sais juste écrire des algos qui tiennent la route.

Citation:

---

il n'existe pas d'algorithme en temps polynomial pour ce problème

---

Cette affirmation n'est pas claire. On parle pour quels types de cas ?
J'affirme qu'il existe un algo polynomial pour "au moins" toutes listes de nombres aléatoires <= (N = 1 000 000 / K = 250 133); Taille <= ceil(N / K); Range(1, 10 000 000); Target === ceil(sum(N) / K); Mémoire < 2go
Ca c'est c'que j'ai moi déjà publié et je parle même pas de ce que j'ai dans le tiroir...

Citation:

---

C'est une notion très théorique et inattaquable par des expériences, uniquement par des preuves mathématiques

---

Oui mais concurrencée par des démonstrations comme les miennes. D'oû le sujet de ce post.

Citation:

---

Une expérience plus intéressante sur tes algos : sont-ils exacts ?

---

Je n'ai publié sur ces pages que des solutions exactes (et les listes de nombres sont datées du même jour de publication). Ceux qui les ont téléchargées et vérifiées savent...

Citation:

---

je suppose que le résultat n'est pas toujours parfait.

---

Le problème c'est pas qu'il soit parfait mais au moins perfectible.
Tout dépend de l'amplitude (intervalle) des nombres. Même si un algo ne boucle pas parfaitement sur les derniers, une simple correction suffit pour atteindre la perfection.

Mes 2 algos sont au pire Quadratique > O(n²) donc polynomiaux (et nécessitent peu de mémoire). Encore un fois tout dépend pour quels types de cas.

Salut

selon l'enoncé c'est les 2 cas
le meme nombre d'elements pour chaque categorie
et la meme valeur
ce qui resonnablement semble peu probable a realiser
amoins d'avoir un nombre d'element divisible par le nombre de cathegorie
et une repartition homogene de valeurs