Suggeritore di parole dati un numero n di caratteri

di
stefanoferrario
il
4 risposte
S
stefanoferrario
Pochi posts
Iscritto da
dic, 2015
Messaggi:
26

Suggeritore di parole dati un numero n di caratteri

Ciao a tutti!
Devo realizzare un suggeritore di parole che dati un certo numero di caratteri n elabora tutte le possibili combinazioni in k gruppi con k <=n.

Ho scritto una funzione che però presenta il problema di richiedere parecchio tempo quando il numero di caratteri supera gli 8... Ovviamente le parole da elaborare sono parecchie tuttavia mi chiedevo se fosse possibile veloccizzare il processo...
vector<string> permutation(int maxLetter){
    vector<string> words;
    char anagrama[18];
    for (int i=0; i<maxLetter; i++){
        anagrama[i]='a'+i;
    }

    int len = strlen(anagrama);
    sort(anagrama, anagrama+len);
    do {
        words.push_back(anagrama);
        sort(words.begin(), words.end());
    } while (next_permutation(anagrama, anagrama+len)); //vengono elaborate tutte le permutazioni di carateri n=maxLetter

    vector<string> temp1;                       //Utilizzando due vettori vado a togliere da ogni parola del primo vettore il carattere finale e lo inserisco nel secondo vettore
    for (int i=0; i<words.size(); i++){         //Terminata l'operazione aggiungo al vettore words le parole trovate e proseguo togliendo nuovamente un carattere
        temp1.push_back(words[i]);
    }
    vector<string> temp2;

    for (size_t k=temp1[0].size(); k>2; k--){
        for (size_t i=0; i<temp1.size(); i++){
            string temp="";
            for (size_t y=0; y<k-1;y++){
                temp+=temp1.at(i)[y];
            }
            if (!verify(temp, temp2)) {
                temp2.push_back(temp);
                sort(temp2.begin(), temp2.end());
            }
        }
        temp1.clear();
        for (int j=0; j<temp2.size(); j++){
            words.push_back(temp2[j]);
            temp1.push_back(temp2[j]);
        }
        temp2.clear();
    }
    temp1.clear();
    temp2.clear();

    return words;
}


grazie!!

4 Risposte

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Suggeritore di parole dati un numero n di caratteri

    Scusa, ma non ho ben capito qual è lo scopo della funzione, potresti essere più chiaro?

    Cosa intendi di preciso con:
    dati un certo numero di caratteri n elabora tutte le possibili combinazioni in k gruppi con k <=n
    ?
  • S
    stefanoferrario
    Pochi posts
    Iscritto da
    dic, 2015
    Messaggi:
    26

    Re: Suggeritore di parole dati un numero n di caratteri

    In pratica date le seguenti lettere dato un numero n di lettere
    n=7 -> abcdefg
    n=9 -> abcdefghi
    ...
    considerando ora n=7 la funzione elabora tutte le combinazioni possibili di queste lettere in stringhe di 7 caratteri. poi prosegue con tutte le combinazioni possibili dei 7 caratteri in stringhe formate da 6... e così via fino alle combinazioni dei 7 caratteri in stringhe di 2 caratteri.

    In pratica poi la funzione mi servirà per stampare tutte le parole che si possono formare utilizzando (tutte o solo alcune) le lettere dell'alfabeto date.


    Questo è un esempio di come dovrebbe funzionare (sono già state escluse tutte le stringhe relative alle combinazioni di caratteri non presenti nel dizionario italiano) :
    Lettere dell'alfabeto date:
    | P | U | S | I | C | K | R |

    Parole suggerite
    USCIR
    SCURI
    SCIUP
    RIUSC
    PURI
    USCI
    SPIR
    CUPI
    CURI
    RUPI
    PUR
    PIU
    USI
    SUI
    SCI
    CUI
    PU
    PI
    SU
    SI
    CI
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Suggeritore di parole dati un numero n di caratteri

    Ok, lo scopo del programma l'ho capito, il codice che hai postato non molto invece!

    Ho provato anche io ad implementare qualcosa, ti posto il codice: 
    #include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

void anagrammi(const string &lettere, const vector<unsigned int> &v, vector<string> &parole)
{
    string s;
    for(unsigned int i = 0; i < v.size(); ++i)
    {
        s.push_back(lettere[v[i]]);
    }
    do
    {
        parole.push_back(s);
    }
    while(next_permutation(s.begin(), s.end()));
}

void combinazioni(string lettere, vector<string> &parole)
{
    vector<unsigned int> v;
    unsigned int i;
    unsigned int j;
    bool flag;
    sort(lettere.begin(), lettere.end());
    for(unsigned int k = lettere.size(); k > 1; --k)
    {
        v.resize(0);
        i = k - 1;
        flag = true;
        for(j = 0; j < k; ++j)
        {
            v.push_back(j);
        }
        while(true)
        {
            if(flag)
            {
                anagrammi(lettere, v, parole);
                flag = false;
            }
            if(v[i] < i + lettere.size() - k)
            {
                ++v[i];
                flag = true;
                if(i != k - 1 && v[i] != v[i + 1] - 1)
                {
                    for(j = i + 1; j < k; ++j)
                    {
                        v[j] = v[j - 1] + 1;
                    }
                    i = k - 1;
                }
            }
            else
            {
                if(i)
                {
                    --i;
                }
                else
                {
                    break;
                }
            }
        }
    }
}

int main()
{
    string lettere = "cane";
    vector<string> parole;
    combinazioni(lettere, parole);
    for(unsigned int i = 0; i < parole.size(); ++i)
    {
        cout << parole[i] << endl;
    }
}
    Sembra funzionare, magari provalo e fammi sapere.
  • S
    stefanoferrario
    Pochi posts
    Iscritto da
    dic, 2015
    Messaggi:
    26

    Re: Suggeritore di parole dati un numero n di caratteri

    Ho implementato il codice nel programma e funziona benone! Sembra essere più rapido di quello di prima! Grazie!!
Devi accedere o registrarti per scrivere nel forum
4 risposte