Générer tous les tableaux de k éléments <= à k

Version imprimable

Bonjour,
Avec des amis nous participons au Project Euler. Pour ceux qui ne connaîtraient pas, c'est tout simplement des problèmes mêlant informatique et mathématiques.
Nous en sommes au problème 88 et nous avons bien progressé, cependant nous sommes face à une petite difficulté. Je précise que l'objet de ma question n'est pas d'avoir une réponse toute faite, mais simplement d'avoir une piste ou des conseils.

L'algo que nous avons imaginé comporte cette partie:

Pour un k donné, on génère des listes d'au plus k chiffres dont le produit P doit être k <= P <= 2k
Exemple, pour k = 3 : (6), (5), (4), (3), (3, 2), (2, 2). Il n'est pas forcément obligatoire d'avoir des listes de tailles différentes si cela rend l'algorithme trop compliqué. Les listes peuvent toutes être composées de 3 chiffres en remplissant les chiffres manquants par des 1. Je pourrais par la suite exploiter ces listes avec une fonction supplémentaire.

Le soucis est que je n'arrive pas à trouver un algorithme efficace qui permettrait de générer ces listes. Sur le papier j'ai ça:
Code:

1 2 3 4 5 6 7 8 9 Pour k = 2: <div style="margin-left:40px">4 * 4 n'est pas dans les bornes : (4, 4) n'est pas une liste valide 4 * 3 .. 4 * 2 .. 4 * 1 est dans les bornes : (4, 1) est une liste valide 3 * 3 ... ... Au final, (4, 1) (3, 1) (2, 2) (2, 1) sont les listes valides pour k = 2</div>
J'ai l'impression que la solution est plutôt simple, sur papier ça fonctionne, mais je n'arrive pas à généraliser pour n'importe quel k, sachant que ce k doit varier entre 2 et 12 000.

J'ai pensé à utiliser un nombre de k chiffres que j'incrémenterai de 1 à chaque tour de boucle et que je pourrais convertir en caractères individuels. Cela me générerai entre autres les listes dont j'ai besoin, mais aussi des listes qui ne remplissent pas les conditions requises. Le temps d'exécution serait médiocre...

Auriez-vous des conseils ou des pistes à me donner ?
Merci d'avance.

22/10/2018, 15h35
tatayo

Bonjour,

Citation:

Envoyé par blenderiste09

Pour un k donné, on génère des listes d'au plus k chiffres dont le produit P doit être k <= P <= 2k
Exemple, pour k = 3 : (3); (3, 2); (2, 2); (2, 2, 2).

Je vois déjà un problème ici, à moins que je n'ai pas compris.
Si je prends le dernier exemple, le produit vaut 8 (2*2*2), alors qu'il doit être compris entre 3 et 6 (3 et 2*3).

Tatayo.
22/10/2018, 17h04
blenderiste09

Effectivement, j'ai fait une erreur. C'est corrigé, merci :)
22/10/2018, 17h35
tbc92

Prenons k = 100 pour l'exemple.
On va considérer que la solution (28,3) et la solution (3,28) sont considérées comme 2 solutions différentes, on les veut toutes les 2.
On va considérer aussi que le nombre 1 est exclu de l'étude. Les solutions (3,1,28) ou (3,28,1) ou (1,1,1,3,1,1,1,1,28,1,1,1,1,1,1,1,1) ne nous intéressent pas ; Ces 3 solutions se résument à (3,28).

Du coup, je te propose de chercher toutes les solutions avec un seul nombre (si k=100, il y en a 199, chacun des nombres entre 2 et 200).
Puis à partir de ce listing, chercher toutes les solutions avec 2 nombres.
Puis à partir des solutions avec 2 nombres, chercher toutes les solutions avec 3 nombres... etc etc ...
Pour k=100, des solutions avec 7 nombres, il y en a peu : (2,2,2,2,2,2,2), (2,2,2,2,2,2,3), (2,2,2,2,2,3,2) et les autres permutations avec 6 fois le nombre 2, et 1 fois le nombre 3.

Ici, je recherche toutes les combinaisons dont le produit est inférieur ou égal à 2*k ; je ne prend pas la contrainte k<=P
Comme ça, je peux réutiliser les combinaisons avec n éléments pour chercher les combinaisons avec n+1 éléments.

A partir de ce recensement, afficher uniquement les combinaisons qui vérifient en plus la condition k<=P, c'est simple.

Même pour k=12000, on va avoir des listes de longueur très raisonnable ; pour k=12000, ln(24000)/ln(2) = 14.55, et donc on aura au max 14 nombres dans notre listes (2*2*2*2 ... répété 15 fois, ça fait plus que 24000)

Ici, une piste, c'est la récursivité (faire une procédure qui s'appelle elle-même)
22/10/2018, 18h10
Flodelarab
Bonjour :coucou:

Pour ouvrir tes horizons, je propose le contraire.
1. Considère 2 sacs. Un sac de solutions à creuser, et un sac de solutions finies.
2. Tu prends une solution à creuser ...
3. ... si la quantité max de nombres n'est pas atteinte ...
4. tu rajoutes un nombre.
5. Si le résultat est supérieur à 2*k, tu bazardes la solution à creuser.
6. Si le résultat est entre k et 2*k, tu mets une version dans le sac des solutions et une version dans le sac des solutions à creuser.
7. Si le résultat est inférieur à k, tu mets cette version dans le sac des solutions à creuser.
8. Quand tu n'as plus rien à creuser, c'est fini, et tu as toutes tes solutions dans le sac des solutions.
9. Sinon (plus de places), tu bazardes la solution et tu reviens à l'étape 2.
23/10/2018, 10h36
Nebulix

facteurs premiers

Chacun de tes produits pourra s'écrire 2^x2*3^x3*5^x5*7^x7. Les nombres premiers de plus d'un chiffre sont exclus.Les facteurs 2^2 et 3^2 peuvent aussi s'écrire 4 et 9, 2^3 peut s'écrire de 4*2,2*4 ou 8.
Il faut faire une quadruple boucle où x2 varie de 0 à trunc(ln(k)/ln(2)) (13 si k=12000), x3 de 0 à trunc( ( ln(k)-x2*ln(2)) /ln(3)), etc
23/10/2018, 14h19
Flodelarab

Citation:

Envoyé par Nebulix

Les nombres premiers de plus d'un chiffre sont exclus.

Pourquoi ?
Si k=13, la liste (2,13) n'est-elle pas une liste valide ?
23/10/2018, 16h22
Nebulix

Citation:

Envoyé par Flodelarab

Pourquoi ?
Si k=13, la liste (2,13) n'est-elle pas une liste valide ?

Le post original parle de "des listes d'au plus k chiffres". 13 est un nombre de deux chiffres donc exclu, si j'ai bien compris le problème. L'auteur du premier post est prié de préciser.
24/10/2018, 14h55
anapurna

salut

salut

en suivant le liens d'euler j'ai trouvé ici l’énoncé du problème
K donne le nombre d’éléments permettant la décomposition du nombre cherché
le but étant de trouver la combinaison tels que la somme des nombres correspondent au produit de ces même nombre

PS :

Citation:

a*b*c*...*n = a+b+c+...+n
ou => a*b*c*...*n -(a+b+c+...+n ) = 0
24/10/2018, 15h40
tbc92

Effectivement, avec l'énoncé précis, la question n'a plus rien à voir !!!

Je reformule :
Un nombre N est dit Somme_produit d'ordre k, s'il peut être décomposé en une somme de k nombre, et un produit des k mêmes nombres.
Exemple :
6=1+2+3 = 1*2*3 : 6 est donc un nombre somme-produit d'ordre 3.
12=1+1+1+1+2+6=1*1*1*1*2*6 : 12 est donc un nombre somme-produit d'ordre 6.
8=1+1+2+2+2 = 1*1*2*2*2 : 8 est donc un nombre somme-produit d'ordre 5.
10=1+1+1+2+5=1*1*1*2*5 : 10 est aussi un nombre somme-produit d'ordre 5.

Pour chaque ordre k, on a éventuellement plusieurs nombres somme-produit d'ordre k. ( Exemple , pour K=5, on a les 2 solutions données ci-dessus 8 et 10).
On définit pour chaque k , le Minumum-somme-produit, C'est le nombre N le plus petit, qui soit un nombre somme-produit d'ordre k. Par exemple, pour k=5, on va trouver 8, et non 10.

MSP(2)=4=2+2=2*2
MSP(3)=6=1+2+3=1*2*3
MSP(4)=8=1+1+2+4=1*1*2*4
MSP(5)=8=1+1+2+2+2=1*1*2*2*2
MSP(6)=12=1+1+1+1+2+6=1*1*1*1*2*6

Puis pour chaque nombre, on définit la somme des MSP, sans double compte.
SMSP(6)=4+6+8+12=30 : C'est la somme des MSP(k), pour k entre 2 et 6. Mais sans double compte : MSP(4)=8, et MSP(5) = 8 également ; 8 sera compté une seule fois dans la somme.

Avec toutes ces définitions, on demande de calculer SMSP(12000)

Calculer le MSP (= le Minimum des nombres Somme-Produit) , pour une valeur de k, ça se fait bien. Mais le traitement dure 1 seconde , voire plus quand k devient grand (k au delà de 1000).
Donc organiser le traitement en se disant : pour une valeur de k, je calcule SMP[k], et je boucle là-dessus, ça va être horriblement long.

Entre le calcul de MSP[1000] et le calcul de MSP[1001], il y a plein de calculs intermédiaires qui sont strictement les mêmes.
Il faut donc organiser le traitement différement.
- Recenser 'toutes' les combinaisons de nombres. ATTENTION, on s'intéresse uniquement aux combinaisons de nombre strictement supérieurs à 1. Le nombre 1 sera utilisé pour 'compléter' les chaines.
- Pour chaque combinaison , calculer la somme S, calculer le produit P, et calculer le nombre d'éléments N
Forcément S<=P. Notons D=P-S.
Avec cette combinaison, complétée avec D fois le nombre 1, on a un tableau de N+D éléments, et par construction, le produit des éléments de ce tableau est égal à la somme des éléments de ce tableau.
Donc ce tableau est un postulant pour être le Minimimum-Somme-produit pour la longueur N+D

Ainsi, avec une seule grosse boucle, on calcule le MSP de tous les nombres entre 2 et 12000 , sans avoir à répéter les mêmes traitements 12000 fois.

Ca nous donne un truc comme ça pour les dernières lignes :
Code:

1 2 3 4 5 6 7 8 9 10 11 k=11990 MSP[k] = 12064 2,2,4,13,58 complété avec 11985 fois le nombre 1 k=11991 MSP[k] = 12064 2,2,2,2,13,58 complété avec 11985 fois le nombre 1 k=11992 MSP[k] = 12084 2,3,38,53 complété avec 11988 fois le nombre 1 k=11993 MSP[k] = 12054 3,7,14,41 complété avec 11989 fois le nombre 1 k=11994 MSP[k] = 12096 3,3,16,84 complété avec 11990 fois le nombre 1 k=11995 MSP[k] = 12096 2,3,28,72 complété avec 11991 fois le nombre 1 k=11996 MSP[k] = 12064 16,26,29 complété avec 11993 fois le nombre 1 k=11997 MSP[k] = 12054 6,7,7,41 complété avec 11993 fois le nombre 1 k=11998 MSP[k] = 12096 2,2,3,12,84 complété avec 11993 fois le nombre 1 k=11999 MSP[k] = 12054 2,3,7,7,41 complété avec 11994 fois le nombre 1 k=12000 MSP[k] = 12096 2,2,4,9,84 complété avec 11995 fois le nombre 1
Comment ça se lit : pour k = 11990, le tableau de 11990 entiers qui donne la somme minimale, et somme=Produit, c'est le tableau composé de 2,2,4,13,58 complété avec 11985 fois le nombre 1 ; Et la somme des nombres en question donne 12064.
Effectivement 2*2*4*13*58, ça donne 12064 (et multiplié par 1 plein de fois, ça reste 12064)
Et 2+2+4+13+58+11985, ça donne aussi 12064.

Et au final, la solution de l'exercice est ... (je ne la donne pas :) )

26/10/2018, 13h22
blenderiste09

Bonjour à tous,

Tout d'abord, merci beaucoup pour vos réponses, on a eu matière à réfléchir. Et désolé de n'avoir pas répondu, j'ai été assez occupé durant ces derniers jours.

Au cours de nos essais et recherches, nous avons essayés plusieurs approches. Tout d'abord la génération de toutes les possibilités de chiffres, {2} {2, 2} {2, 2, ..., 2} {3} etc...

Citation:

- Recenser 'toutes' les combinaisons de nombres. ATTENTION, on s'intéresse uniquement aux combinaisons de nombre strictement supérieurs à 1. Le nombre 1 sera utilisé pour 'compléter' les chaines.

Nous ne sommes pas arrivés à générer toutes ces possibilités, nous avons passés plusieurs jours à essayer différentes manières de faire. Pourtant, j'ai l'impression que c'est quelque chose d'assez simple...
D'après ce que nous avons pu trouver, il s'agit de lister toutes les combinaisons de k parmis n avec répétition et où k = n. Cependant, la plupart des ressources que j'ai pu trouver parle de la manière de les compter, en non pas de les générer.
Si nous arrivons à le faire, nous utiliserons sûrement quelque chose comme l'a conseillé tbc92.

Du coup, nous avons tenté une autre approche.
Nous cherchons des chiffres dont le produit est égal leur somme. Nous cherchons donc une factorisation. Partant de cela, nous avons calculé la factorisation en facteurs premiers d'un nombre n = k. De cette factorisation, l'idée que nous avons est de générer toutes les façons de "combiner" ce produit de facteur.
Par exemple pour n = 12: 12= 2² x 3
Les possibilités sont : {2 x 2 x 3}, {4 x 3}, {2 x 6}, {12}. Une fois ces factorisations trouvées, on fait la somme de chacune et on regarde si S == P. Si oui, on a trouvé n minimum pour k. Sinon, on incrémente n et on refait.
Encore une fois, j'ai fait pas mal de recherche sur l'internet mondial pour trouver des pistes, et ce que j'ai pu trouver c'est que le problème sus-mentionné s'appelle le multiplicative partition ou multiset factoring. Mais tout ce que j'ai vu comme algorithmes sont des algorithmes qui sont soit mal implémentés (ont des erreurs, etc...) soit sont rédigés dans des langages illisibles pour moi par exemple içi :?.

Auriez-vous un algorithme à conseiller pour l'une où l'autre des manières que l'on essaie d'approcher (génération de toutes les listes ou multiplicative partition) ?

Merci encore à vous