[C++] Generare stringhe in modo ordinato

[2000Diego]

Salve a tutti, sto scrivendo un programmino in c++ e mi serve avere tutte le combinazioni possibili di caratteri fino a stringhe da 20. Ho pensato vari sistemi ma nessuno funzionava. Non pubblico i tentativi perché sarebbe inutile dato che sono solo spezzoni di codice senza scopo!
Sapreste dirmi come posso fare?
Ringrazio in anticipo.

[oregon]

In teoria ti bastano 20 for

[minomic]

Ti posto un esempio sul quale puoi lavorare:

#include <iostream>

void incrementa_contatore (int* array, int size) {
    int tmp;
    array[size-1]++;    // uno scatto
    tmp = size-1;
    while (array[tmp] == 26) {    // faccio scattare i precedenti
        array[tmp] = 0;
        array[tmp-1]++;
        tmp = tmp-1;
    }
}


char* genera_stringa_da_array (int* array, int size) {
    char* stringa = new char[size];
    for(int i = 0; i < size; ++i) {
        stringa[i] = 'a' + array[i];
    }
    return stringa;
}


bool controlla_termine (int* array, int size) {
    for(int i = 0; i < size; ++i) {
        if(array[i] != 26)
            return false;
    }
    return true;
}


int main(int argc, char const *argv[])
{
    char* stringa;
    int* array = new int[5];
    for(int i = 0; i < 5; ++i) {
        array[i] = 0;
    }

    while (!controlla_termine (array, 5)) {
        stringa = genera_stringa_da_array (array, 5);
        std::cout << stringa << std::endl;
        incrementa_contatore (array, 5);
    }

    return 0;
}

L'idea che ci sta dietro è quella di non gestire un array di caratteri ma un array di interi. Poi fai corrispondere ad ogni intero una lettera. Se lo metti dentro a un ciclo for per la lunghezza, dovresti riuscire a generare tutte le combinazioni per tutte le lunghezze.

Visto che l'ho scritto un po' di fretta ci potrebbero essere degli errori... Nel caso dimmelo!

[oregon]

In tutti i casi, se devi fare un "brute force" per trovare una password di 20 caratteri, ne hai tempo ...

[minomic]

In tutti i casi, se devi fare un "brute force" per trovare una password di 20 caratteri, ne hai tempo ...

Sì, la stessa cosa che ho pensato io... Considerando una password di 20 caratteri, le combinazioni sono 26^(20), che è circa 2*10^(28). E solo considerando le minuscole! Se poi si considerano anche la maiuscole e i numeri allora le possibilità sono un numero piuttosto mostruoso...

[minomic]

Come sospettavo, nel codice che avevo postato prima c'era un errore. In particolare era sbagliato il controllo che facevo per vedere se avevo esaminato tutte le possibili combinazioni.

Adesso dovrebbe essere corretto:

#include <iostream>

void incrementa_contatore (int* array, int size) {
    int tmp;
    array[size-1]++;    // uno scatto
    tmp = size-1;
    while (tmp != -1 && array[tmp] == 26) {    // faccio scattare i precedenti
        array[tmp] = 0;
        array[tmp-1]++;
        tmp = tmp-1;
    }
}


char* genera_stringa_da_array (int* array, int size) {
    char* stringa = new char[size];
    for(int i = 0; i < size; ++i) {
        stringa[i] = 'a' + array[i];
    }
    return stringa;
}


bool controlla_termine (int* array, int size) {
    for(int i = 0; i < size; ++i) {
        if(array[i] != 0)
            return false;
    }
    return true;
}


int main(int argc, char const *argv[])
{
    char* stringa;
    const int SIZE = 4;
    int* array = new int[SIZE];
    for(int i = 0; i < SIZE; ++i) {
        array[i] = 0;
    }

    do {
        stringa = genera_stringa_da_array (array, SIZE);
        std::cout << stringa << std::endl;
        incrementa_contatore (array, SIZE);
    } while (!controlla_termine (array, SIZE));

    return 0;
}

[2000Diego]

si, l'idea iniziale era di fare un brute force ma solamente a scopo dimostrativo. Comunque ho risolto riadattando il codice di Minomic, grazie mille a entrambi.