Algoritmo per formare tutte le possibili parole

di il
6 risposte

Algoritmo per formare tutte le possibili parole

Salve, ho una matrice di caratteri in cui devo trovare tutte le parole di 4 lettere adiacenti(anche con un angolo in comune sono considerate adiacenti) che si possono formare... ES:

      A  S  S  D 
      S  B  E  Y
      G  F  O  I
      H  U  U K

ASGU    SABO    FOIK    FEBS    SYDE    HUFO
mi basterebbe un algoritmo che cerchi tutte le parole di 4 lettere a partire da una lettera, così potrei ciclare l algoritmo stesso per ogni lettera della matrice....
fino ad ora non sono riuscito ad implementare un algoritmo decente... ho scelto una strada secondo me molto complicata: ho "trasformato" la matrice in un "grafo", "numerando" tutte le lettere che sono state quindi convertite in NODI... ho quindi la matrice delle adiacenze che mi dice tutte le lettere adiacenti ad una lettera... ho creato una piccola funzione all interno della classe che restituisce il primo nodo adiacente ad un nodo, se ce ne sono di non visitati.. altrimenti restituisce -1 se tutti i nodi adiacenti sono stati visitati.. per fare ciò mi sono servito di un array di bool e una funzione che imposta i nodi come visitati/non visitati... questo è il codice che ho sviluppato fino ad ora anche se non mi convince molto... qualcuno ha qualche idea migliore, oppure riesce ad implementare la funzione mancante?


struct Nodo  //PER OGNI NODO ABBIAMO LA RIGA E COLONNA CORRISPONENTE ALLA MATRICE INIZIALE
		{
		int r;
		int c;
		};

class MatriceAd  //CLASSE CONTENENTE LA MATRICE D'ADIACENZA CREATA CON IL COSTRUTTORE 
	{
	private:
		bool M[16][16];
		bool visitati[16];
	public:
		MatriceAd()
			{
			for(int i=0; i<16; i++)
				for(int j=0; j<16; j++)
					M[i][j]=false;			
			int num=0;
			for(int i=0; i<4; i++)
				for(int j=0; j<4; j++, num++)
					{
					if(i-1>=0)
						{
						M[num][num-4]=true;
						if(j-1>=0)
							M[num][num-5]=true;
						if(j+1<4)
							M[num][num-3]=true;
						}			
					if(j-1>=0)
						M[num][num-1]=true;
					if(j+1<4)
						M[num][num+1]=true;
					if(i+1<4)
						{
						M[num][num+4]=true;
						if(j-1>=0)
							M[num][num+3]=true;
						if(j+1<4)
							M[num][num+5]=true;
						}
					}
			}

	int primoAd(int i)
		{
		for(int j=0; j<16; j++)
			if(M[i][j]==1 && visitati[j]==false)
				return j;
		return -1;
		}

	void visitato(int i, bool b) {visitati[i]=b;}	
	
	void svuota() {for(int i=0; i<16; i++) visitati[i]=false;}

	};

void parole(int, vector<Nodo>, char[][4], MatriceAd);

int main()
	{
	MatriceAd m;
	char Matrice[4][4] = {{'D','F','F','B'},
	         		      {'T','U','G','I'},
		         	      {'O','K','J','M'},
			              {'K','M','B','E'}};
	
	vector<Nodo> nodi;   //VETTORE DEI NODI
	Nodo n;
	for(int i=0; i<4; i++)
		for(int j=0; j<4; j++)
			{
			n.r=i;
			n.c=j;
			nodi.push_back(n);
			}
	 
	for(int i=0; i<16; i++)  //CICLO LA FUNZIONE SEGUENTE PER OGNI NODO i
		parole(i, nodi, Matrice, m);    //FUNZIONE DA IMPLEMENTARE
	
	}



	void parole(int i, vector<Nodo> nodi, char Matrice[4][4], MatriceAd m)
		{	
	
	        }
	

6 Risposte

  • Re: Algoritmo per formare tutte le possibili parole

    Ecco un esempio completo e funzionante che stampa tutte le parole:
    
    #include <algorithm>
    #include <vector>
    #include <iostream>
    using namespace std;
    
    struct Cell
    {
        int x;
        int y;
        Cell(int a, int b) { x = a; y = b; }
        bool operator == (const Cell& c) { return (x == c.x) && (y == c.y); }
        bool IsValid() const { return (x >= 0) && (y >= 0) && (x < 4) && (y < 4); }
    };
    
    class Word: public vector<Cell>
    {
    public:
        bool Add(const Cell& c)
        {
            // se non valido o già presente
            if (!c.IsValid() || (std::find(begin(), end(), c) != end()))  
                return false;
    	
             push_back(c);
             return true;
        }
    };
    
    void Complete(Word word, int x, int y, vector<Word>& list)
    {
        if (!word.Add(Cell(x, y)))
            return;
    
        if (word.size() == 4)
        {
            list.push_back(word);
            return;
        }
    
        for(int i = -1; i <= 1; ++i)
            for(int j = -1; j <= 1; ++j)
                Complete(word, x + i, y + j, list);
    }
    
    int main()
    {
        // ottiene le posizioni di tutte le possibili parole 
        vector<Word> words;
        for(int x = 0; x < 4; ++x)
            for(int y = 0; y < 4; ++y)
                Complete(Word(), x, y, words);
    
        // applica il risultato ad una matrice specifica e stampa le parole
        char matrice[4][4] = {
            {'I','G','R','A'},
            {'F','I','N','O'},
            {'N','S','E','R'},
            {'V','O','N','O'}
        };
    
        for (vector<Word>::iterator i = words.begin(); i != words.end(); ++i)
        {
            for (Word::iterator j = i->begin(); j != i->end(); ++j)
                cout << matrice[j->x][j->y];
            cout << " ";
        }
        return 0;
    }
    
    Dato che le parole possibili sono indipendenti da cosa c' è scritto nella matrice ho pensato di calcolare prima le posizioni di tutte le possibili parole e di metterle in un array, poi le applichi ad una matrice particolare, in questo modo se devi ripetere l' operazione su matrici differenti i tempi si riducono notevolmente.

    In una matrice 4x4 dovrebbero esserci 1764 possibili parole di 4 lettere (salvo errori).
    Come vedi il codice è piuttosto piccolo e semplice, se qualcosa non fosse chiaro sono a tua disposizione.
  • Re: Algoritmo per formare tutte le possibili parole

    Grazie mille... ora lo studio un pò... se non dovessi capire qualcosa ti farò sapere... ciao e ancora grazie
  • Re: Algoritmo per formare tutte le possibili parole

    Buongiorno barba59
    Ho visto la tua pagina che hai pubblicato sul web, non so se posso disturbarti per un gioco che devo risovere domenica in una gara particolare.
    Gli organizzatori ci hanno dato un combinatore con 4 rotelline dove sono scritte 8 lettere su ciascuna ruota.
    Provando le combinazioni possibili dovrebbe risultare una parola sensata con 4 lettere.
    Sarebbe possibile ottenere la lista completa delle credo 4096 parole che si potrebbero comporre?
    Le lettere sono:
    1 ruota : CAUSZTRS
    2 ruota : NEDGHOPQ
    3 ruota : PEHFIMTB
    4 ruota : OVNCRZQI
    Beh che posso dirti, se mi dedicherai del tempo per questo non posso che ringraziarti enormemente, sennò pazienza, grazie lo stesso per aver letto il messaggio.
    saluti e grazie ancora

    Luciano
  • Re: Algoritmo per formare tutte le possibili parole

    Quello era un messaggio del 2012 ! 4 anni fa ! E non ha senso riferirti direttamente ad un utente che ha risposto 4 anni fa !
  • Re: Algoritmo per formare tutte le possibili parole

    Si hai ragione, come posso fare per chiedere aiuto?
    grazie mille
    Luciano
  • Re: Algoritmo per formare tutte le possibili parole

    Come tutti nel forum. Crea un nuovo thread, spiega il problema ma non chiedere la soluzione pronta (è vietato). Indica cosa hai scritto tu e se hai avuto errori.
Devi accedere o registrarti per scrivere nel forum
6 risposte