Discussion :

[Guesset]

Bonjour tbc92,

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.

[mllm_so]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[laurent_ott]

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.

[tbc92]

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.

[mllm_so]

@laurent_ott

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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" ?

[mllm_so]

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...

[dourouc05]

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).

[mllm_so]

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.

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...

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.

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...

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.

[anapurna]

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