IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Août 2009
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2009
    Messages : 14
    Points : 3
    Points
    3
    Par défaut 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.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 032
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 032
    Points : 9 331
    Points
    9 331
    Par défaut
    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 ?
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    Août 2009
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2009
    Messages : 14
    Points : 3
    Points
    3
    Par défaut
    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.

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 032
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 032
    Points : 9 331
    Points
    9 331
    Par défaut
    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

Discussions similaires

  1. Réponses: 4
    Dernier message: 27/05/2010, 10h07
  2. [MySQL] Requête pour récupérer les 5 derniers enregistrement dans l'ordre croissant
    Par Jonathan.b dans le forum PHP & Base de données
    Réponses: 6
    Dernier message: 07/01/2008, 10h50
  3. Obtenir les colonnes d'une table par ADO dans l'ordre croissant
    Par soso78 dans le forum VB 6 et antérieur
    Réponses: 1
    Dernier message: 11/11/2007, 18h59
  4. Réponses: 3
    Dernier message: 24/02/2007, 16h21
  5. Dans quel ordre ranger les vertices ?
    Par legend666 dans le forum OpenGL
    Réponses: 5
    Dernier message: 10/10/2005, 11h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo