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 :

Permutation alphanumérique


Sujet :

Algorithmes et structures de données

  1. #1
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut Permutation alphanumérique
    Bonjour à tous(tes),
    Quelqu'un aurait un algo de permutation en pseudo-code.
    Pour une chaine de caractères a$ de longueur n avec f=n!
    Sans doublons si possible
    J'ai la première ligne
    Pour x=1 to f
    Gros merci aux savants.
    Savoir pour comprendre et vice versa.

  2. #2
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 771
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 771
    Points : 11 991
    Points
    11 991
    Par défaut
    Bonjour

    J'ai la première ligne
    Pour x=1 to f
    Il ne faut pas mettre la réalisation avant la conception.


    De plus, ta question est sibylline.
    Dans quel contexte es-tu ? Et que cherches-tu à faire ?


    Normalement, on permute de la façon suivante, que ce soit des nombres, des lettres, ou des cageots de fraises :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    temp <- a
    a <- b
    b <- temp
    En Perl, on utiliserait une syntaxe comme celle-ci:
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Je cherche à avoir toutes les combinaisons d'une chaine de caractères
    Je sais que par exemple pour 6 caractères je dois avoir 720 combinaisons (6!)
    J'en conclus donc que je dois faire 720 traitements
    D'où une boucle de 720 pas
    C'est pas ça ?
    Savoir pour comprendre et vice versa.

  4. #4
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 771
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 771
    Points : 11 991
    Points
    11 991
    Par défaut
    En un mot, tu cherches les anagrammes.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  5. #5
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    On peut l'appeler comme ça, sauf qu'il n'y aura pas que des lettres.
    Je cherche une explication claire des opérations à effectuer.
    Pour parvenir au but.

    EDIT:C'est bon pour l'instant, je fouille le forum avec "anagramme" et je trouve pas mal de choses.
    Savoir pour comprendre et vice versa.

  6. #6
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 771
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 771
    Points : 11 991
    Points
    11 991
    Par défaut
    Citation Envoyé par valentin03 Voir le message
    Pour parvenir au but.
    Le but n'a jamais été exprimé.



    Si c'est pour éviter les doublons car tu considères 2 ensembles comme identiques à une permutation près, le conseil est de trier et comparer. Ne va pas t'amuser à lister les anagrammes.
    Si le but est de comparer à un dictionnaire, le conseil est parfois de partir du dictionnaire et d'écrire une fonction de comparaison, entre ta réglette de départ et ton entrée de dictionnaire, qui détermine s'ils sont anagrammes l'un de l'autre.
    Si tu veux lister les possibilités, tu as déjà vu un concours de beauté.... 4ème dauphine .... 3ème dauphine .... 2ème dauphine .... 1ère dauphine .... Miss France ! Tu dois faire pareil.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  7. #7
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Puisque tu veux connaître le but final, le voici:
    Je veux, à partir d'une expression du genre: "x=a+(b*c) (en restant conscient que le nombre de caractères sera forcément limité par n!)
    Obtenir les expressions équivalentes de toutes les variables de l'expression.
    Pour ce faire je compte utiliser la force brute, à savoir:
    Donner des valeurs numériques arbitraires aux variables.
    Calculer x
    Faire la combinatoire des variables, opérateurs et parenthèses
    Eliminer les incohérents (+=)a(b...)
    Calculer, comparer, extraire.
    Le tout pour le fun, of course.
    Savoir pour comprendre et vice versa.

  8. #8
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 184
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 184
    Points : 2 291
    Points
    2 291
    Billets dans le blog
    9
    Par défaut Permutation alphanumérique
    Bonjour,

    Au moins, c'est plus clair, et cela peut de simplifier dans la mesure où:
    1) la chaîne commence obligatoirement par 'x=';
    2) les parenthèses sont inutiles dans l'exemple donné, puisque
    'x=a+b+c' a un sens, de même que 'x=a+b*c' , 'x=a*b+c' , 'x=a*b*c' ... si tu te limites aux deux opérations mentionnées.
    3) les symboles des nombres alternent nécessairement avec ceux des signes: 'x=u#v#w' .

    Les contraintes grammaticales limitent ainsi drastiquement le nombre de possibilités: 3! * 22 = 24 .

    Cependant, en relisant un détail de ton dernier message
    Citation Envoyé par valentin03 Voir le message
    ... Faire la combinatoire des variables, opérateurs et parenthèses ...
    je crains qu'il n'arrive de sérieuses complications.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Je ne veux pas limiter à l'expression donnée en exemple, mais limiter aux quatre opérateurs.
    Je veux voir combien de caractères seront prohibitifs pour le temps de calculs.
    Ce qui impliquera d'optimiser le code (ce qui est la moitié du but).
    Je crois me souvenir que tu m'a donné il y a un moment un code en Windev, que la version d'évaluation n'a pas voulu lancer; et qui malgré mes efforts m'est resté obscur (Windev, c'est spécial...)
    Savoir pour comprendre et vice versa.

  10. #10
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 184
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 184
    Points : 2 291
    Points
    2 291
    Billets dans le blog
    9
    Par défaut Permutation alphanumérique
    Tu as déjà (je m'en souviens) amené un sujet apparenté, mais je ne t'ai sûrement pas suggéré un code écrit en Windev (que je ne pratique pas, et ne connais que de nom) ...

    L'introduction des parenthèses va s'accompagner d'une liste considérable d'incompatibilités. Y a-t-eu un peu réfléchi ?

    Ne vaudrait-il pas mieux commencer par des choses simples, par exemple des lettres et les quatre signes d'opérations ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 268
    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 : 3 268
    Points : 7 494
    Points
    7 494
    Par défaut
    Je recopie :
    Je veux, à partir d'une expression du genre: "x=a+(b*c)
    Obtenir les expressions équivalentes de toutes les variables de l'expression.
    Si je comprend bien, à partir de x=a+(b*c)
    Les solutions que tu veux sont :
    a=x-(b*c)
    b=(x-a))/c
    c=(x-a)/b

    C'est à dire isoler à chaque fois une des variables, et l'écrire en fonction des 3 autres.

    Accessoirement, on peut lister d'autres réponses : a = x-(c*b) par exemple, mais je pense que celle-ci ne t'intéresse pas, car doublon avec a=x-(b*c)

    j'imagine que ton besoin, c'est ça. En tout cas, ton besoin était celui là il y a un an ( cf : https://www.developpez.net/forums/d1...nnees/jouable/ ) , et à l'époque, tu n'avais pas obtenu tout à fait la réponse voulue.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  12. #12
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    @: wiwaxia: En traitant les parenthèses à part ça paraît faisable. De toutes façons, des parenthèses il ne peut pas y en avoir beaucoup parce qu'avec plus de 10 caractères ça doit devenir ingérable au niveau temps.
    @: tbc92: C'est bien ce que j'espère.
    Savoir pour comprendre et vice versa.

Discussions similaires

  1. Permuter deux variables sans variable temporaire
    Par khayyam90 dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 09/01/2015, 08h02
  2. Réponses: 6
    Dernier message: 28/12/2004, 16h09
  3. [Perf] Permuter un tableau
    Par seb-astien dans le forum Collection et Stream
    Réponses: 7
    Dernier message: 25/08/2004, 19h31
  4. Permuter un tableau
    Par seb-astien dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 25/08/2004, 16h40
  5. [Algo] Permutations et arrangements
    Par rbag dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 13/10/2003, 11h40

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