Anagrammi e ricorsione

di il
6 risposte

Anagrammi e ricorsione

Ciao, sto realizzando un programma che, data una parola, ne scriva tutti gli anagrammi possibili (anche la parola stessa). Devo utilizzare un metodo ricorsivo ed è la prima volta che ne realizzo uno, quindi sono un po' in difficoltà.
Ho due problemi: il primo è che il programma mi stampa un numero di anagrammi a caso, il secondo è che non ho la più pallida idea di come fargli fare tutti gli anagrammi che servono! Qualcuno può darmi una mano?


import java.util.ArrayList;
import java.util.List;

public class AnagrammiModel {
	
	private char[] arrayChar ;
	private List<String> anagrammi = new ArrayList<String>();
	
	
	public AnagrammiModel(String parola) {
		
		//modifico la parola in un array di char
		arrayChar = parola.toCharArray();
		
		//aggiungo la parola alla lista degli anagrammi
		anagrammi.add(parola);
		
		int livello = 1;
		
		//for(int i = 0; i < fatt(parola.length()); i++) per fargli scrivere n! anagrammi, ma non dà il risultato voluto
			generaAnagramma(arrayChar, livello, 0);
		
	}
	

	private void generaAnagramma(char[] arrayChar, int livello, int letteraDaCuiPartire) { //questo è il mio metodo ricorsivo
		
		if(livello == arrayChar.length) {
			
			System.out.println(anagrammi);
			return ;
			
		}
		
		for( int i = letteraDaCuiPartire; i < livello; i++ ) {
			if(livello < arrayChar.length-1)
				arrayChar = cambiaOrdine(i, livello+1);
			
			if(isNew(arrayChar)) {
				String anagramma = "";
				for(int j = 0; j < arrayChar.length; j++)
					anagramma += arrayChar[j];
				anagrammi.add(anagramma);
			}
			
			generaAnagramma(arrayChar, livello+1, letteraDaCuiPartire+1);
			
		}
	}
	
	//controlla se ho già scritto quell'anagramma
	private boolean isNew(char[] arrayChar) {
		
		String anagramma = "";
		for(int j = 0; j < arrayChar.length; j++)
			anagramma += arrayChar[j];
		
		if(!anagrammi.contains(anagramma))
			return true;
		
		return false;
	}

	private char[] cambiaOrdine(int c, int d) {
		
		char temp = arrayChar[c];
		arrayChar[c] = arrayChar[d];
		arrayChar[d] = temp;
		
		return arrayChar;
		
	}
	
	//metodo che realizza il fattoriale
	private int fatt(int length) {
		int fatt = 1;
		
		for(int i = 1; i <= length; i++)
			fatt = fatt*i;
		
		return fatt;
	}

}

public class TestAnagramma {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		AnagrammiModel am = new AnagrammiModel("ciao");
	}

}
Se passo con il main "ciao" mi fa 2 anagrammi, se passo "eat" me ne fa 1

6 Risposte

  • Re: Anagrammi e ricorsione

    whisky ha scritto:


    Ciao, sto realizzando un programma che, data una parola, ne scriva tutti gli anagrammi possibili (anche la parola stessa). Devo utilizzare un metodo ricorsivo ed è la prima volta che ne realizzo uno, quindi sono un po' in difficoltà.
    Non ho letto tutto il tuo codice (ma solo per mancanza di tempo ora) però posso darti qualche indizio: hai usato una forma del metodo ricorsivo che è

    private void generaAnagramma(char[] arrayChar, int livello, int letteraDaCuiPartire)

    Credo si possa sicuramente arrivare alla soluzione con questa forma ma .... puoi provare con qualcosa di decisamente più semplice, del tipo

    private List<String> generaAnagramma(String str)

    Ti posso assicurare che si arriva alla soluzione in maniera abbastanza facile (e oltretutto SENZA dover fare cose particolari come quel contains o swap di caratteri).

    Prova a pensarci.
  • Re: Anagrammi e ricorsione

    Innanzitutto grazie per la risposta, quello che mi consigli quindi è di passare come parametro la lista contenente gli anagrammi... E quindi ad ogni iterazione il metodo aggiunge alla lista il nuovo anagramma, giusto?
    Per quanto riguarda il contains e swap ci penserò su, ma ora come ora non mi viene in mente altro
  • Re: Anagrammi e ricorsione

    whisky ha scritto:


    quello che mi consigli quindi è di passare come parametro la lista contenente gli anagrammi...
    No, guarda bene. Il metodo ricorsivo riceve una stringa e restituisce una lista. Chiaramente man mano che si "scende" nella ricorsione, la stringa passata sarà più corta e la lista restituita più parziale.
  • Re: Anagrammi e ricorsione

    andbin ha scritto:


    whisky ha scritto:


    quello che mi consigli quindi è di passare come parametro la lista contenente gli anagrammi...
    No, guarda bene. Il metodo ricorsivo riceve una stringa e restituisce una lista. Chiaramente man mano che si "scende" nella ricorsione, la stringa passata sarà più corta e la lista restituita più parziale.
    Hai ragione, penso di aver capito. Domani proverò a scrivere il codice, sperando di non fare stupidaggini
  • Re: Anagrammi e ricorsione

    Ho provato a seguire il tuo consiglio, ma c'è proprio qualcosa che non riesco a capire
    A parte il fatto che non sono riuscito a mettere in pratica il tuo suggerimento
    e oltretutto SENZA dover fare cose particolari come quel contains o swap di caratteri)
    (di questo vorrei occuparmene alla fine), provando a debuggare ho visto che esegue la ricorsione il numero giusto di volte, però c'è qualcosa di sbagliato all'interno dell'algoritmo: mi crea solo n anagrammi (con n intendo la lunghezza della parola), fa sempre gli stessi swap tra le lettere ma non capisco dove sbaglio!
    
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class AnagrammiModel {
    	
    	
    	private char[] arrayChar ;
    	private List<String> anagrammi ;
    	
    	
    	public AnagrammiModel(String parola) {
    		
    		anagrammi = new ArrayList<String>();
    		
    		//modifico la parola in un array di char
    		arrayChar = parola.toCharArray();
    		
    		//aggiungo la parola alla lista degli anagrammi
    		anagrammi.add(parola);
    		
    		int livello = 0;
    		
    		//for(int i = 0; i < fatt(parola.length()); i++) per fargli scrivere n! anagrammi, ma non dà il risultato dovuto
    			//generaAnagramma(arrayChar, livello, 0);
    		generaAnagramma(parola, livello);
    		
    	}
    	
    	private List<String> generaAnagramma(String parola, int livello){
    		
    		if(livello == fatt(parola.length()) -1) {
    			System.out.println(anagrammi);
    			return anagrammi;
    		}
    		
    		
    		for(int i = 0; i < parola.length()-1; i++)
    			arrayChar = cambiaOrdine(i, i+1);
    		
    		if(isNew(arrayChar)) {
    			String anagramma = "";
    			for(int j = 0; j < arrayChar.length; j++)
    				anagramma += arrayChar[j];
    			anagrammi.add(anagramma);
    		}
    		
    		generaAnagramma(parola, livello+1);
    		
    		return null;
    	}
    	
    
    	private boolean isNew(char[] arrayChar) {
    		
    		String anagramma = "";
    		for(int j = 0; j < arrayChar.length; j++)
    			anagramma += arrayChar[j];
    		
    		if(!anagrammi.contains(anagramma))
    			return true;
    		
    		return false;
    	}
    
    	private char[] cambiaOrdine(int c, int d) {
    		
    		char temp = arrayChar[c];
    		arrayChar[c] = arrayChar[d];
    		arrayChar[d] = temp;
    		
    		return arrayChar;
    		
    	}
    	
    	private int fatt(int length) {
    		int fatt = 1;
    		
    		for(int i = 1; i <= length; i++)
    			fatt = fatt*i;
    		
    		return fatt;
    	}
    
    }
    
  • Re: Anagrammi e ricorsione

    whisky ha scritto:


    Ho provato a seguire il tuo consiglio, ma c'è proprio qualcosa che non riesco a capire
    A parte il fatto che non sono riuscito a mettere in pratica il tuo suggerimento
    Guarda che non serve affatto calcolare il fattoriale, né sarebbe davvero necessario ragionare in termini di array di char (e quindi neanche di "swap").
Devi accedere o registrarti per scrivere nel forum
6 risposte