Générer dans un ordre croissant les n-uplets «appliqués» à un tableau de valeurs

Bonjour/Bonsoir,

Est-il possible de générer dans un ordre croissant les n-uplets «appliqués» à un tableau de valeurs ?

Exemple: Soit un tableau trié T=[3,8,9,10,15] avec les triplets dans l'ordre lexicographique on obtient:
T[0]*T[1]*T[2]=3*8*9=216
T[0]*T[1]*T[3]=3*8*10=240
T[0]*T[1]*T[4]=3*8*15=360
T[0]*T[2]*T[3]=3*9*10=270
…
T[2]*T[3]*T[4]=9*10*15=1350

Les valeurs obtenues en «composant» les 10 combinaisons ne sont pas ordonnées: 216,240,360,270,405,450,720,1080,1200,1350
J'ai pris un exemple avec des triplets mais je cherche quelque chose qui fonctionnerait avec des quadruplets, quintuplets... Le but étant de compter les n-uplets «composés» qui ne dépassent pas une certaine limite.

En bénéficiant de l'ordre, il n'y aurait pas toutes les combinaisons à générer/stocker/trier, on s'arrête quand on atteint la limite.

Vous remerciant par avance pour vos idées.

Générer les n-uplets dans l'ordre, ce n'est pas possible. Pour avoir les n-uplets dans l'ordre, il faut générer tous les n-uplets, puis trier le tableau obtenu. Donc pas efficace du tout pour ton besoin.

Il faut chercher d'autres pistes. Sur ton exemple,on prend des 3-uplets parmi un ensemble de 5 valeurs. Dans la vraie vie, à la place de 3 parmi 5, quels sont les ordres de grandeur ?
Et dans l'ensemble de 5 valeurs, est-ce qu'il peut y avoir des valeurs en double ?

Bonjour,

Merci pour votre réponse, c'est bien ce que je craignais.
Pour l'ordre de grandeur, potentiellement des millions de combinaisons... (pas de valeurs en double)

J'ai juste remarqué que les valeurs «*composées*» sont ordonnées par «*paquets*», en effet, générer les combinaisons pour un n-uplet revient a faire des boucles imbriquées et dans la boucle centrale les résultats sont ordonnés et avec un «*break*» on peut sortir de la boucle dés que l'on dépasse la limite. On peut donc «*sauter*» de paquet en paquet sans tout parcourir.

Le problème, c'est que ne sachant pas à l'avance si je vais avoir besoin de triplets, 4-uplets, 5-uplets... je ne peux pas utiliser des boucles imbriquées. Je dois les simuler (simulated nested loop) et pour l'instant, je n'arrive pas à transposer le principe du «*break*» à la façon dont je génère les combinaisons.

Ca, ça doit se faire.
En général, je n'utilise pas Break mais i = valeur_max_i + 1 ; ce qui permet de sortir de la boucle

Ensuite, pour optimiser, il y a quelques pistes :
- Traiter les nombres du plus grand au plus petit. Le fait de sélectionner ou non tel grand facteur va peser très lourd sur le résultat. Et on pourra plus vite déterminer si on est au-dessus du seuil ou non. Utile dans l'absolu. Inutile , voire contre-productif si tu appliques le conseil 3.

- Si le seuil choisi est relativement grand (en théorie, sur l'exemple, le seuil devrait être de puissance ( 3*8*9*10*5 ; 3/5 ), tu as intérêt à calculer le nombre de combinaisons plus grandes que ce seuil, et non le nombre de combinaisons plus petites. Puis tu obtiendras le résultat voulu par une soustraction. En fait, si tu appliques les 2 conseils suivant, celui-ci n'a plus aucun intérêt, et complique inutilement le traitement.

- mémoriser au tout début du traitement des points de repères : le produit de k facteurs parmi les x facteurs restants est compris entre PMin[k,x] et Pmax[k,x] ; Ainsi tu pourras plus vite détecter, pour un groupe donné, si ce groupe est tout entier valide, ou tout entier invalide, ou bien, si on a besoin de creuser plus. Ainsi, tu pourras sortir des boucles par anticipation dans 2 cas : Quand tu sais que tout un groupe sera valide, et quand tu sais que tout un groupe sera invalide.

- Par sécurité, il faut calculer le nombre de combinaisons valides et le nombre de combinaisons invalides. Ca permet de vérifier que le compte est bon.