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 :

Optimiser un code de combinaison pour toutes les longeurs de mots de 1 à 12 caractères


Sujet :

Algorithmes et structures de données

  1. #21
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 607
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 607
    Points : 188 574
    Points
    188 574
    Par défaut
    Pour y aller de manière itérative, c'est le même principe que le code récursif : la boucle extérieure itère sur le numéro du caractère qui sera ajouté, la boucle intérieure sur tous les caractères potentiels, une troisième boucle sur tous les mots de longueur inférieure, où on génère enfin un nouveau mot. En pseudo-Python (non testé, donc), la troisième boucle correspondant à une compréhension de liste :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    generated = [[""]]
    for i in range(1, 12): 
        for c in 'a' upto 'z': 
            generated[i] = [w + c for w in generated[i - 1]]

    Maintenant, si tu veux le code le plus rapide pour générer ces séquences de longueur constante, le mieux est probablement d'écrire explicitement tes douze boucles, puis de laisser le compilateur faire son travail (le code sera nettement plus simple, pas d'histoire d'accumulateur ou que sais-je, ses heuristiques d'optimisation pourront fonctionner à plein).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  2. #22
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Transcris ce code C testé (qui est celui que j'avais donné en pseudo code)
    Attention en C on commence les tableaux à 0.
    Ne fonctionne pas si len est plus grand que 256.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void toutes_les_combinaisons(char *ch, int len)
    {
        char nch[256] = {0};
        int ind[256] = {0};
        int lench = strlen(ch);
     
        for(int i = 0; i < len; i++)
            nch[i] = ch[0];
     
        int i = len-1;
        while(i >= 0)
        {
            puts(nch);
            ind[i]++;
            while (i >= 0 && ind[i] >= lench)
            {
                ind[i] = 0;
                nch[i] = ch[ind[i]];
                i--;
                if (i >= 0)
                    ind[i]++;
            }
            if (i >= 0)
            {
                nch[i] = ch[ind[i]];
                i = len-1;
            }
        }
    }
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  3. #23
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    Novembre 2010
    Messages
    3 035
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3 035
    Points : 8 400
    Points
    8 400
    Par défaut
    Citation Envoyé par toni___ Voir le message
    Quelqu'un aurait-il un code propre sans récursivité testé et qui fonctionne bien ?
    toujours dans la même discussion

  4. #24
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par toni___ Voir le message
    Quelqu'un aurait-il un code propre sans récursivité testé et qui fonctionne bien ?
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int ALPHABET_LENGTH = 3;
    char[] alphabet = {'a','b','c'};
     
    int WORD_LENGTH = 6;
    char[] word = new char[WORD_LENGTH];
     
    int N = (int)Math.pow(ALPHABET_LENGTH, WORD_LENGTH);
    for(int i=0; i<N; i++) {
     
        for(int j=0,value=i; j<WORD_LENGTH; j++,value/=ALPHABET_LENGTH)
            word[j] = alphabet[ value % ALPHABET_LENGTH ];
     
        // your code here...
    }

    L'idée c'est simplement d'énumérer les valeurs de 1 à N, puis d'écrire cette valeur en base A (A = taille de l'alphabet) sur W chiffres (W = taille du mot).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #25
    Membre à l'essai
    Homme Profil pro
    autre
    Inscrit en
    Avril 2016
    Messages
    34
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autre
    Secteur : Conseil

    Informations forums :
    Inscription : Avril 2016
    Messages : 34
    Points : 10
    Points
    10
    Par défaut
    En fait ce n'est calculable, car les combinaisons me serve à essayer de retrouver mon mot de passe perdu, d'une application que j'ai créé en MS Access.

  6. #26
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 033
    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 033
    Points : 9 333
    Points
    9 333
    Par défaut
    C'est parfaitement calculable.
    Nombre de caractères 'utilisables' dans un mot de passe : à toi de dire, disons 70.
    Nombre de mots de passe possibles, avec une longueur de 1 caractère : N1=70
    Nombre de mots de passe possibles, avec une longueur de 2 caractères : N2=70*70
    Nombre de mots de passe possibles, avec une longueur de 3 caractères : N3=70*70*70

    Nombre de mots de passe possibles, avec une longueur de 12 caractères : N12=70*70*70*70*70*70*70*70*70*70*70*70
    Cumul = N1+N2+N3 ...+N12

    Malheureusement (ou plutôt heureusement), ce nombre est très grand. Si tu peux tester 1000 combinaisons par secondes, il va te falloir plusieurs années pour tester toutes les combinaisons possibles.
    Si tu sais que les derniers caractères, c'est soit ton prénom, soit ton nom, et qu'il faut chercher uniquement les 5 ou 6 caractères restants, tu réduis nettement le nombre de combinaisons, tu le divises par quelques millions.


    Récursivité ou pas, ce n'est pas la question. La question, c'est que tester quelques milliards de milliards de combinaisons, c'est long.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #27
    Membre à l'essai
    Homme Profil pro
    autre
    Inscrit en
    Avril 2016
    Messages
    34
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autre
    Secteur : Conseil

    Informations forums :
    Inscription : Avril 2016
    Messages : 34
    Points : 10
    Points
    10
    Par défaut
    Bonjour,
    Merci pour ta réponse.

    J'ai une idée de la combinaison à trouver :
    sa longeur est entre 8 et 12 caractères et le champ des possibilités du vecteur de départ, j'ai pu le réduire à 24 caractères au lieu de 104.

    Donc cela fait encore beaucoup de combinaisons.

  8. #28
    Membre à l'essai
    Homme Profil pro
    autre
    Inscrit en
    Avril 2016
    Messages
    34
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autre
    Secteur : Conseil

    Informations forums :
    Inscription : Avril 2016
    Messages : 34
    Points : 10
    Points
    10
    Par défaut
    Citation Envoyé par tbc92 Voir le message
    Si tu peux tester 1000 combinaisons par secondes, il va te falloir plusieurs années pour tester toutes les combinaisons possibles.
    Je peux tester 278 combinaisons /seconde, ce n'est pas assez rapide !

    pour tester le password à ma db j'utilise la ligne de code suivante :
    Set db = acc.DBEngine.OpenDatabase(strDbName, False, False, ";PWD=" & strPassword)

    qui je pense est une méthode DAO ?

    Peut-être je dois trouver une autre façon de faire que cette ligne de code pour gagner en rapidité d'exécution ?

    Merci à chacun d'entre vous
    pour vos exemples de codes avec ou sans récursivité.

  9. #29
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 607
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 607
    Points : 188 574
    Points
    188 574
    Par défaut
    Citation Envoyé par toni___ Voir le message
    Peut-être je dois trouver une autre façon de faire que cette ligne de code pour gagner en rapidité d'exécution ?
    Oui, très clairement : générer des combinaisons ne sera pas un facteur limitant (c'est extrêmement rapide si tu ne fais qu'itérer sur toutes les lettres pour une longueur donnée). Pour ça, demande plutôt sur un forum orienté bases de données… (Réfléchis aussi à du parallélisme.)
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  10. #30
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    103
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 103
    Points : 110
    Points
    110
    Par défaut
    Bonjour,

    Voici un petit code R qui affiche le ou les n-ièmes mots en utilisant l'alphabet fourni.
    L'idée est de convertir le nombre n dans une base b où b est le nombre de lettres de l'alphabet.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     
       GetWords <- function(n, k, alphabet = c('a', 'b')) {
         ## Get the n-nth words with k letters using a given alphabet.
         stopifnot( n >= 0, length(k) == 1, k > 0, length(alphabet) > 0)
         m <- length(alphabet);
         ## Get a single word
         GetWord <- function(x) {
           ## Create an empty word filled with '0'
           word <- rep(alphabet[1], k)
           i <- k
           ## Convert the number 'x' to base 'm'
           while(x > 0) {
             word[i] <- alphabet[(x %% m)+1]
             i <- i - 1;
             x <- x %/% m
           }
           return(paste(word, collapse =''))
         } 
         ## Get all words (vectorized loop)
         sapply(n, GetWord)
       }
     
      ## Convert to binary
      GetWords(1:10, k=4)
      ## Convert to decimal
      GetWords(5:10, k=4, alphabet=0:9)
    Je ne connais pas VBA, mais il ne devrait pas y avoir de problème particulier pour traduire le code.

    Ce code plus général sera efficace, mais il peut être optimisé pour des mots consécutifs.

Discussions similaires

  1. Un seul code pour toutes les feuilles
    Par NEC14 dans le forum Macros et VBA Excel
    Réponses: 12
    Dernier message: 16/05/2013, 17h46
  2. [XL-2010] Un seul code VB pour toutes les feuilles
    Par juan67 dans le forum Macros et VBA Excel
    Réponses: 14
    Dernier message: 11/02/2013, 17h45
  3. Incorporer un code dans un module pour toutes les pages
    Par jlb59 dans le forum VB 6 et antérieur
    Réponses: 8
    Dernier message: 20/02/2012, 06h17
  4. Code qui permet de garder BO ouvert pour toutes les macros
    Par Alexandra0907 dans le forum Macros et VBA Excel
    Réponses: 13
    Dernier message: 21/05/2008, 13h56
  5. Algo pour toutes les combinaisons possibles
    Par rantanplan08 dans le forum Général Java
    Réponses: 6
    Dernier message: 03/01/2008, 10h45

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