Challenge mathématique #39 : Combinaisons de cadeaux de noël

[emmanuel-fr]

Défi de Noêl ! 

La partition des nombres est le nombre de possibilités de découpages et d’arrangements d’un élément qui au départ est entier. Par exemple, prenez 4 boites contenant des cadeaux de noël, vous pouvez les mettre toutes ensemble superposées ou une d’un côté et 3 autres ensembles ou deux et deux ensembles ou encore chacune des boites séparées etc… en fait il y a 5 possibilités avec 4 boites. Mais combien de possibilités peut-on avoir avec 10 boites ? et plus…100 ? cela s’appelle la partition des entiers.

Voici le défi : écrire un algorithme LabVIEW strict et exact (pas une approximation statistique) qui compte combien de partitions on peut obtenir avec un nombre défini de cadeaux de noël de départ. 

Le but est d’avoir une chaine de sortie avec le nombre de départ et le nombre de partitions possibles. (Voir VI joint)

Par exemple pour 5 cadeaux, la chaine de sortie doit comporter la valeur de départ puis les décompositions dans un ordre logique comme suit (dit ordre lexicographique) avec les chiffres, le symbole plus et un \n retour chariot à la fin de chaque ligne.

    5

    4+1

    3+2

    3+1+1

    2+2+1

    2+1+1+1

    1+1+1+1+1

Non seulement le découpage a un ordre particulier à décomposer, mais le nombre de décompositions augmente très rapidement (par exemple pour un nombre de 100 cadeaux, nous avons 190569292 partitions possibles, aussi vous serez limité en taille de calcul et par l’affichage en sortie. Essayez d’atteindre un nombre le plus grand possible, en limitant l’affichage dans la chaine de caractères à 1000 lignes.

L’algorithme sera validé pour des nombres allant jusqu’à 100 cadeaux et 1000 lignes de décompositions qui permet de vérifier les combinaisons.

Ce mois-ci un dernier livre LabVIEW  2eme édition à gagner. Le gagnant sera tiré au sort (basé sur les sorties du loto) sur les codes validés.

Envoyez votre code nommé Ch39_Partitions_Votre Pseudo.vi à emmanuel.roset@ni.com avant le 6 janvier. Et postez sur la communauté « code envoyé » pour vérifier la boite email en cas de non réception. Postez aussi vos commentaires sur la progression ou questions relatives au défi !

Bonne récréation LabVIEW de décembre rempli de cadeaux à partitionner ! 

Les réponses sont publiées. L'extension de fichier est .arch désolé car il n'accepte plus les fichiers .zip donc il suffit de le renommer en .zip avant de l'ouvrir, il a simplement été renommé.

[Nico_EMC]

Emmanuel, l'ordre des nombre n'est pas important ? Par exemple, on considère que 4+1 et 1+4 sont la même chose?

[emmanuel-fr]

En fait si, car il faudra que je compare les résulats finaux assez automatiquement, donc la logique qui a été donnée en exemple est a respecter. Le premier chiffre de la colonne est décroissant puis on prend le chiffre le plus grand possible en 2 eme position etc.. comme une décomposition. C'est pour cela que j'ai inclus dans les règles "dans l'ordre logique comme suit..."

[Nico_EMC]

Code envoyé. Par contre, il va faloir que j'optimise un peu : il me faut plus d'une demi-heure pour traiter les 100 paquets...

[emmanuel-fr]

Reçu, officiellement épaté par la rapidité de réalisation du code

Pour l'exécution c'est plutot déjà bien ! on arrive dans des temps corrects a exécuter 70 sur mon PC portable Core i7

On remarquera que cela dessine un demi sapin de noel avec les +1+1...

[emmanuel-fr]

Codes du challenge 38 précédent publiés

[PhilB58]

Bonjour Emmanuel,

pourrais-tu mettre la série de chaines en partant de 10, j'ai un peu de mal à la reconstituer à la main (sur Excel), alors si je pars sur une fausse piste, j'aurai encore plus de mal à trouver le bon algo.
Ça doit faire une petite 40aine de lignes 🙂

Merci

[Nico_EMC]

Tu veux ça :

10
9+1
8+2
8+1+1
7+3
7+2+1
7+1+1+1
6+4
6+3+1
6+2+2
6+2+1+1
6+1+1+1+1
5+5
5+4+1
5+3+2
5+3+1+1
5+2+2+1
5+2+1+1+1
5+1+1+1+1+1
4+4+2
4+4+1+1
4+3+3
4+3+2+1
4+3+1+1+1
4+2+2+2
4+2+2+1+1
4+2+1+1+1+1
4+1+1+1+1+1+1
3+3+3+1
3+3+2+2
3+3+2+1+1
3+3+1+1+1+1
3+2+2+2+1
3+2+2+1+1+1
3+2+1+1+1+1+1
3+1+1+1+1+1+1+1
2+2+2+2+2
2+2+2+2+1+1
2+2+2+1+1+1+1
2+2+1+1+1+1+1+1
2+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1

[emmanuel-fr]

ah ben c'est fait Merci Nico_EMC !

(on voit bien la moitié du sapin)

[Julien_V.]

Bonjour,

Code envoyé.

[PhilB58]

merci Nico_EMC (et Emmanuel aussi, tu l'aurais fait 😉 )

[emmanuel-fr]

PhilB58 merci  en effet je ne publie pas de challenges sans avoir testé et obtenu les réponses avant et aussi pour savoir si c'est faisable et en combien de temps. Par contre j'optimise très peu. Le plus long est de recevoir tous les codes et de les vérifier

[PhilB58]

Tracasse pas, pour mon code, tu vas attendre parce que je sèche là 😞
Rien à faire je tourne en rond, pas moyen de touver une piste ... mais bon, j'imagine que je vais finir par y arriver tout de même 🙂

[Michael.C]

Pareil, je sèche, j'arrive à gérer jusqu'à 5, et après mon algorithme mange certains cas... Par exemple pour le cas 6, j arrive pas à gérer les valeurs (3+3 & 2+2+2)....

[Nico_EMC]

Bon, j'ai eu un peu de mal aussi. J'ai été obligé de passer par récurence, avec un vi réentrant pour y arriver. Si ça peut vous aider ...

[Michael.C]

Je me doute qu'il y a une solution par là, mais pour l'instant, je cherche une autre méthode ^^. Je pense pas être loin d'y aboutir, juste que les vacances arrivant vendredi, beaucoup de chose à finaliser, et donc pas beaucoup de temps pour jouer 😄

[emmanuel-fr]

Ok je me doute que les congés vont poser quelques soucis, donc on repousse la fin du défi au 6 janvier

[Michael.C]

Merci pour le geste Emmanuel 🙂 Après si j'ai pas le temps de poster un code ce n'est pas grave. Je cherche avant tout à m'amuser et à améliorer mon approche algorithmique en faisant les challenges. J'ai pu constaté qu'il y a un sacré écart avec le niveau présenté lors du challenge précédent, l'analyse des codes fournis m'a permis de voir plein de chose intéressante :D PS: Je sais pas trop où mettre cela, mais je voulais signaler un petit bémol sur la nouvelle interface de cette partie du forum, lorsque j'écris des messages, impossible de revenir à la ligne, c'est dérangeant. De plus, lors de l'arrivée d'un nouveau message, le sujet concerné n'est pas mis en avant (titre en gras/icone différente/...), cela gêne un peu pour l'ergonomie et pour repérer rapidement quel sujet est en cours. Pour info, je suis sous Firefox/Windows 7. Bonne journée.

[emmanuel-fr]

Merci pour les précieux retours sur la nouvelle interface. Depuis quelle a été mise à jour des ajustements sont a réaliser. Je ferai les retours, donc n'hésitez pas à me donner des détails, voir directement sur mon adresse emmanuel.roset@ni.com

Pour le délai supplémentaire c'est aussi pour que tout le monde puisse profiter des fêtes

[PhilB58]

Un retour également sur la nouvelle interface: avec l'ancienne, je ne devais pas me connecter à chaque fois, quand je voulais poster un message, avec cette nouvelle mouture, chaque fois que je viens jeter un oeil, je suis d'office déconnecté ???!!!???

Puis pareil que Michael.C, les challenges sont pour moi un amusement et une manière de progresser, .... par contre, je n'ai pas de soucis pour passer à la ligne 😉

[Michael.C]

Un problème qui parait simple, mais qui te fait des noeuds au cerveau... Maintenant mon algo arrive à répartir jusqu'à n=7, puis à n=8, je passe en boucle infini -_-..

[Michael.C]

Je pense enfin l'avoir eu 😄

Par contre j'en suis à 115 minutes pour 100 cadeaux avec 82528 possibilités.

Ca serait possible de m'envoyer le cas 100 😄 Histoire que je vérifie avant d'envoyer mon code 🙂

EDIT : je viens de relire l'énoncé qui annonce 190569292 possibilités pour 100 cadeaux :'(....

Pourtant j'avais pu le valider jusqu'à 10 sans problème ....

Nico tu pourrais m'envoyer en mp la réponse du 50 voir si ca marche à ce niveau là 🙂 pour moi ca prend 50secondes à faire.

[emmanuel-fr]

Voici les premiers jusqu'à 89 en partant de 100

100
99+1
98+2
98+1+1
97+3
97+2+1
97+1+1+1
96+4
96+3+1
96+2+2
96+2+1+1
96+1+1+1+1
95+5
95+4+1
95+3+2
95+3+1+1
95+2+2+1
95+2+1+1+1
95+1+1+1+1+1
94+6
94+5+1
94+4+2
94+4+1+1
94+3+3
94+3+2+1
94+3+1+1+1
94+2+2+2
94+2+2+1+1
94+2+1+1+1+1
94+1+1+1+1+1+1
93+7
93+6+1
93+5+2
93+5+1+1
93+4+3
93+4+2+1
93+4+1+1+1
93+3+3+1
93+3+2+2
93+3+2+1+1
93+3+1+1+1+1
93+2+2+2+1
93+2+2+1+1+1
93+2+1+1+1+1+1
93+1+1+1+1+1+1+1
92+8
92+7+1
92+6+2
92+6+1+1
92+5+3
92+5+2+1
92+5+1+1+1
92+4+4
92+4+3+1
92+4+2+2
92+4+2+1+1
92+4+1+1+1+1
92+3+3+2
92+3+3+1+1
92+3+2+2+1
92+3+2+1+1+1
92+3+1+1+1+1+1
92+2+2+2+2
92+2+2+2+1+1
92+2+2+1+1+1+1
92+2+1+1+1+1+1+1
92+1+1+1+1+1+1+1+1
91+9
91+8+1
91+7+2
91+7+1+1
91+6+3
91+6+2+1
91+6+1+1+1
91+5+4
91+5+3+1
91+5+2+2
91+5+2+1+1
91+5+1+1+1+1
91+4+4+1
91+4+3+2
91+4+3+1+1
91+4+2+2+1
91+4+2+1+1+1
91+4+1+1+1+1+1
91+3+3+3
91+3+3+2+1
91+3+3+1+1+1
91+3+2+2+2
91+3+2+2+1+1
91+3+2+1+1+1+1
91+3+1+1+1+1+1+1
91+2+2+2+2+1
91+2+2+2+1+1+1
91+2+2+1+1+1+1+1
91+2+1+1+1+1+1+1+1
91+1+1+1+1+1+1+1+1+1
90+10
90+9+1
90+8+2
90+8+1+1
90+7+3
90+7+2+1
90+7+1+1+1
90+6+4
90+6+3+1
90+6+2+2
90+6+2+1+1
90+6+1+1+1+1
90+5+5
90+5+4+1
90+5+3+2
90+5+3+1+1
90+5+2+2+1
90+5+2+1+1+1
90+5+1+1+1+1+1
90+4+4+2
90+4+4+1+1
90+4+3+3
90+4+3+2+1
90+4+3+1+1+1
90+4+2+2+2
90+4+2+2+1+1
90+4+2+1+1+1+1
90+4+1+1+1+1+1+1
90+3+3+3+1
90+3+3+2+2
90+3+3+2+1+1
90+3+3+1+1+1+1
90+3+2+2+2+1
90+3+2+2+1+1+1
90+3+2+1+1+1+1+1
90+3+1+1+1+1+1+1+1
90+2+2+2+2+2
90+2+2+2+2+1+1
90+2+2+2+1+1+1+1
90+2+2+1+1+1+1+1+1
90+2+1+1+1+1+1+1+1+1
90+1+1+1+1+1+1+1+1+1+1

[Julien_V.]

Salut,

Voilà ce que j'ai comme partitions possibles et comme temps :

10 -> 42 / 0.00s
20 -> 627 / 0.01s
30 -> 5604 / 0.02s
40 -> 37338 / 0.03s
50 -> 204226 / 0.09s
60 -> 966467 / 0.40s
70 -> 4087968 / 1.93s
90 -> 56634173 / 29.39s
100 -> 190569292 / 95s
110 -> 607163746 / 327s

A++

[PhilB58]

Bonjour à tous,

Bientôt les réveillons, je suis en congé 🙂 ça fait du bien 🙂
Par contre, j'ai eu beaucoup de problèmes pour trouver une solution, je finissais par partir dans tous les sens sans réussir à finaliser un code qui donnait satisfaction!
Aujourd'hui, c'est chose faite, j'ai un code qui donne le résultat demandé, mais là, il a du mal, j'ai stoppé tout à 741723 cadeaux, et ça m'a pris 220 minutes et des poussières!
J'imagine mal à ce rythme aller jusque 190569292 cadeaux, je n'y serai pas encore avant 2017 😞
Mais bon, le code fonctionne, c'est le principal et je le garde de côté pour présenter à Emmanuel avant le 6 janvier.

Maintenant, optimisation 🙂
Bons réveillon de Noël à tous 🙂

[PhilB58]

Oups, on ne peut pas (plus?) éditer les messages? J'ai fait un grosse faute sur le précédent, ça m'aurait plu de la corriger 😞

[PhilB58]

Bon, je poursuis mon monologue 🙂
J'ai les mêmes résultats en nombre de cadeaux que Julien_V; pour 100, j'obtiens 190569292 cadeaux en 256613ms (mais je suis sur mon vieux pc perso, il a 10 ans aujourd'hui 🙂 )

Par contre, je travaille sur un tableau de num que je dois convertir en chaine avec séparateur à chaque évolution du tableau (une conversion par cadeau), et c'est ça qui me prends du temps 😞

Exemple: pour 50, 204226 cadeaux en 253461ms (plus de 4 minutes) avec conversion pour 312ms sans conversion.
Mais je ne vois pas comment optimiser cette conversion, j'ai utilisé une foncion native LV (sans doute déjà pas mal optimisée).
Par contre, j'ai deux VI assez différents qui fonctionnent 🙂
A+

[PhilB58]

Codes envoyés.

[emmanuel-fr]

Merci PhilB58 codes bien reçu, sur ma machine Core I7  8Go de RAM il prend 152 s pour une valeur 100.

Ce challenge était plus difficile même si sur papier il semblait simple

[David-K]

Code envoyé

Je confirme celui-là était plus costaud que les autres, mais c'était cool comme challenge 

[PhilB58]

"Merci PhilB58 codes bien reçu, sur ma machine Core I7  8Go de RAM il prend 152 s pour une valeur 100."

Emmanuel, 152s pour le plus rapide des deux codes???

[PhilB58]

désolé, mais pn fait comment pour éditer un message??? Je ne trouve pas cette option!!! 😞

[Michael.C]

Bon, et bien je m'avoue vaincu pour celui-ci, j'arrive pas à débuguer mon programme. J'aurai le plaisir de voir les solutions fournis par les autres 🙂

[emmanuel-fr]

Bonjour, les réponses sont publiées. L'extension de fichier est .arch car je suis désolé car il n'accepte plus les fichiers .zip. Donc il suffit de le renommer en .zip avant de l'ouvrir (il a simplement été renommé). Je vais voir avec nos développeurs s'ils peuvent y remédier.

4 personnes ont courageusement relevé le défi qui était un peu plus difficile.

Pour gagner un Livre LabVIEW par tirage au sort, nous prendront le prochain Loto en fonction de ceux qui souhaitent un Livre LabVIEW

Je suppose que Nico ne souhaite pas postuler pour le livre ? Qui n'a pas besoin d'un Livre LabVIEW ?

Pour les codes, beaucoup ont utilisés des VI recustifs. Pour la valeur de 100 qui est très longue à calculer, certains ont fait des optimisations.

Le but étant de croitre en compétences LabVIEW et partager des codes.

Bravo à tous pour avoir participé !

					Decomposition	Test 100
1	Challenge 39_Nico_EMC				OK	OK
2	Ch 39_Partitions_Julien_V.vi				OK	OK (46 sec)
3	Challenge39_David-K				OK	OK
4	Ch 39_PArtitions_PhilB58				OK	OK

[PhilB58]

Perso, le bouquin m'intéresse!

Je ne participe pas aux challenges pour l'avoir, mais je n'ai eu qu'une courte formation LV (juste la LV Core 1), et une bonne lecture ne pourrait que me permettre de progresser!!
Merci Emmanuel 😉

[Julien_V.]

Hello,

Pareil, le bouquin me plairait bien.

Par contre je ne sais pas si j'ai mal vu mais je ne crois pas qu'il y ait les sources des réponses sur le post d'Emmanuel ?

A++

[emmanuel-fr]

Normalement il doit apparaitre sur le post principal ne pièce jointe avec le VI de départ.

[Nico_EMC]

Effectivement, je laisse ma place pour le tirage au sort, ça fait une chance sur 3 pour les autres 🙂

[David-K]

Cool merci Nico 😄

[emmanuel-fr]

OK, le prochain tirage est samedi donc je proposed'utiliser la boule complémentaire, suspense...

chiffres :

1, 2, 3 pour Julien_V,

4, 5, 6 pour David_K

7, 8, 9 pour PhilB_58

[Julien_V.]

---

emmanuel-fr a écrit :

Normalement il doit apparaitre sur le post principal ne pièce jointe avec le VI de départ.

---

Yes ! merci bien.

[PhilB58]

Merci Nico 😉

[Julien_V.]

Merci Nico !

[emmanuel-fr]

Résultats du loto de samedi 14 janvier 2016, le numéro complémentaire chance est le 1 !

Donc le gagnant est Julien_V

Merci a tous d'avoir participé au défi de noel

[Julien_V.]

Salut,

---

emmanuel-fr a écrit :

Résultats du loto de samedi 14 janvier 2016, le numéro complémentaire chance est le 1 !

Donc le gagnant est Julien_V

---

Ça fait plaisir dès le lundi matin !

Merci ! 

[PhilB58]

Bravo à Julien_V 😉 ... et décidément, ce n'est pas encore le moment de jouer au lotto pour moi 😞  😉 😉