Ciao,
sto implementando un suggeritore di parole per il gioco UpWords. Da specifiche mi vengono date in un turno 7 lettere e devo essere in grado di elaborare il miglior suggerimento utilizzando le lettere date più quelle di una parola presente già nel campo da gioco (posso modificarla lasciando almeno un carattere).
Ho deciso di implementare una funzione che mi calcoli tutte le combinazioni possibili di n (7 lettere più quelle della parola presa in considerazione) caratteri in k spazi.
Quindi ho un lungo elenco di combinazioni: abcdefghie ... abcdefghi ... abcdefg ... abcde ... abc... e così via...
La funzione purtroppo risulta già un po' lenta nell'elaborazione di tutte le combinazioni (test con combinazioni di 11 caratteri in k spazi k [11,2])
Questo è il codice per la preparazione delle combinazioni:
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;
}
}
}
}
}
Pensavo poi di eliminare da tali combinazioni tutte quelle in cui le lettere che compongono la parola non sono nella posizione iniziale... per spiegarmi meglio... se ho le tra le lettere disponibili E,A,C,S,M,U,O e la parola nel campo da gioco prese in considerazione è CANE io posso utilizzare le lettere già presenti della parola CANE cambiarne alcun con le lettere che ho a disposizione ma senza cambiare l'ordine di quelle che rimangono...
Una parola che posso comporre sarà quindi "esAmE" composta sostituendo la C e la N di cane con la S e la M che ho a disposizione e aggiungendo davanti la E
Io avevo pensato ad una funzione che passasse in entrata un puntatore al vettore di combinazioni...
char temp_char;
bool check=false;
for (int i=0; i<allComb->size(); i++){
check=false;
for (int k=0; k<allComb->at(i).size(); k++){
if (check){
if (allComb->at(i)[k]>='h'){
if (allComb->at(i)[k]==temp_char+1){
temp_char++;
} else {
allComb->erase(allComb->begin()+i);
break;
}
}
if (allComb->at(i)[k]<'h'){
temp_char++;
}
}
if (!check){
if (allComb->at(i)[k]>='h'){
temp_char=allComb->at(i)[k];
check=true;
}
}
L'esecuzione però mi risulta parecchio lenta e non riesco a capirne il motivo...