Version imprimable
Bonjour tbc92,
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).Citation:
Envoyé par ;12070657
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:
2
3
4
5
6
7
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
J'vous rassure j'en doutais pas, d'autres l'on fait bien avant nous et avec des nombres bien plus grands !Citation:
Moi aussi j'y arrive, exemples parmi d'autres
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)
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.Code:
2
3
4
5
6
7
8
9
10
11
12
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...
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.Citation:
Envoyé par mllm_so
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.
Cette affirmation n'est pas claire. On parle pour quels types de cas ?Citation:
il n'existe pas d'algorithme en temps polynomial pour ce problème
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...
Oui mais concurrencée par des démonstrations comme les miennes. D'oû le sujet de ce post.Citation:
C'est une notion très théorique et inattaquable par des expériences, uniquement par des preuves mathématiques
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:
Une expérience plus intéressante sur tes algos : sont-ils exacts ?
Le problème c'est pas qu'il soit parfait mais au moins perfectible.Citation:
je suppose que le résultat n'est pas toujours parfait.
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