[JAVA]Ordinamento insieme di stringhe

[frankyster]

ciao,
vi espongo brevemente quello che dovrei fare :dati due array di stringhe,(ad esempio)
I1:[j11,j21]
I2:[j12,j22,j32]

j11=abcd
j21=abc
----------
j12=abd
j22=bcd
j32=adc

devo trovare la max lunghezza sottostringa comune tra ogni coppia di stringhe: (e fin qui tutto ok!!)
nel mio caso:
MSC(J11,J12)=2
MSC(J11,J22)=3
MSC(J11,J32)=1
MSC(J21,J12)=2
MSC(J21,J22)=2
MSC(J21,J32)=1

quindi dopo aver trovato le max lunghezze per ogni coppia ,devo ordinare le stringhe nei due array seguendo l'ordine dato dalle lunghezze delle sottostringhe trovate dal piu piccolo valore al piu grande,ad esempio nel mio caso la piu piccola lunghezza(1) si trova in corrispondenza di MSC(J21,J32)=1,quindi inserisco in prima posizione j21 in I1 e j32 in I2 e cosi via fino ad orninare tutte le stringhe..,inoltre le stringhe vanno inserite a coppia nel senso che per ogni coppia se una o entrambe le stringhe sono già stata inserite in uno o entrambi gli array che sto ordinando questa coppia non deve essere inserita..infatti nel mio caso non considero le coppie MSC(J21,J12)=2 e MSC(J21,J22)=2 che dovrei mettere in seconda posizione poichè j21 è gia nell'array I1
quindi il risultato finale dovrebbe essere:
I1= j21 j11
I2= j32 j12 j22

quello che avevo in mente io era questo: trovare la max lunghezza tra la prima coppia di stringhe,quindi inserire queste stringhe negli array,il passo successivo:considerare la successiva coppia e trovare il rispettivo max,confrontare questo nuovo max con il precedente max,se il max attuale è maggiore del precedente allora inserisco le stringhe corrispondenti al max attuale in posizione successiva a quelle gia inserite,mentre se il max corrente è minore del max precedente inserisco le stringhe in posizione precedente a quelle gia inserite...

sto provando a implementare questo algoritmo ma con non poche difficoltà e scarso successo,questo il mio codice che non credo sia molto corretto,infatti non mi ritorna quello che dovrebbe:

public class Ordinamento {
	public static int longestCommonSubstring(String str1, String str2){
		
		if((str1==null && str1.length()==0) || (str2==null && str2.length()==0))
            return 0;
        int[][] num = new int[str1.length()][ str2.length()];
        int maxlen = 0;
        
        for (int i = 0; i < str1.length();i++){
		   for (int j = 0; j < str2.length(); j++){
			   if (str1.charAt(i) != str2.charAt(j))
                            num[i][ j] = 0;
                            else{
								if ((i == 0) || (j == 0))
                                    num[i][ j] = 1;
                                    else
                                    num[i][ j] = 1 + num[i - 1][ j - 1];

                                    if (num[i][ j] > maxlen){
										maxlen = num[i][j];
                                      
                                    }
							}
          }
      }
      return maxlen;
	}
	/*verifica se le stringhe sono uguali*/
	public static boolean uguali(String a,String b){
		boolean uguali;
		if(a.length()== b.length()) {
			uguali = true;
			int i = 0;
			while(uguali && i<a.length()) {
				if(a.charAt(i) != b.charAt(i))
					uguali = false;
				    i = i+1;
		    }
		}
		else /*se t hanno lunghezza diversa, quindi sono diverse */
		uguali = false;
		return uguali;
	}
	

	public static void ordinamento1(String[]I1,String[]I2){
		int i, j, max;
		//int [] maxLunghezzaSottostringa= new int [arrayI1.length * arrayI2.length];
		String [] arrayI1= new String [I1.length];
		String [] arrayI2= new String [I2.length];
		for(i=0;i<arrayI1.length;i++)
			arrayI1[i]=" ";
		for(i=0;i<arrayI2.length;i++)
			arrayI2[i]=" ";
		int maxLunghezzaSottostringa=0;
		max=-1;
		for(i= 0;i<I1.length;i++){
			for(j= 0;j<I2.length;j++){
				maxLunghezzaSottostringa=longestCommonSubstring(I1[i],I2[j]);
				System.out.println(maxLunghezzaSottostringa+" ");
				
				String stringaI1=I1[i];
				String stringaI2=I2[j];
				if(maxLunghezzaSottostringa>=max){
					for(i=0;i<arrayI1.length;i++){
						boolean stringheUguali;
						stringheUguali=uguali(arrayI1[i],stringaI1);
						if(stringheUguali==false &&( stringaI2!=arrayI1[i]))
							arrayI1[i]=stringaI1;
						
						stringheUguali=uguali(arrayI1[i],stringaI2);
						if(stringheUguali==false &&(stringaI1!=arrayI1[i]))
							arrayI1[i]=stringaI2;
					}
					for(j=0;j<arrayI2.length;j++){
						boolean stringheUguali;
						stringheUguali=uguali(arrayI2[j],stringaI1);
						if(stringheUguali==false && (stringaI2!=arrayI2[i]))
							arrayI2[j]=stringaI1;
						
						stringheUguali=uguali(arrayI2[j],stringaI2);
						if(stringheUguali==false && (stringaI1!=arrayI2[i]))
							arrayI2[j]=stringaI2;
					}
					max=maxLunghezzaSottostringa;
					
				}
				else{
					for(i=0;i<arrayI1.length;i++){
						boolean stringheUguali;
						stringheUguali=uguali(arrayI1[i],stringaI1);
						if(stringheUguali==false &&( stringaI2!=arrayI1[i]))
							//sposto gli elementi dell'array di una posizione a destra
							for(i=0;i<arrayI1.length;i++){
								arrayI1[i+1]=arrayI1[i];
							}
							arrayI1[i]=stringaI1;
						
						stringheUguali=uguali(arrayI1[i],stringaI2);
						if(stringheUguali==false &&(stringaI1!=arrayI1[i]))
							for(i=0;i<arrayI1.length;i++){
								arrayI1[i+1]=arrayI1[i];
							}
							arrayI1[i]=stringaI2;
					}
					for(j=0;j<arrayI2.length;j++){
						boolean stringheUguali;
						stringheUguali=uguali(arrayI1[j],stringaI1);
						if(stringheUguali==false && (stringaI2!=arrayI1[i]))
							for(i=0;i<arrayI2.length;j++){
								arrayI1[j+1]=arrayI1[j];
							}
							arrayI1[j]=stringaI1;
						
						stringheUguali=uguali(arrayI1[j],stringaI2);
						if(stringheUguali==false && (stringaI1!=arrayI1[i]))
							for(i=0;i<arrayI2.length;j++){
								arrayI1[j+1]=arrayI1[j];
							}
							arrayI1[j]=stringaI2;
					}
				}
					
			}
			for(j=0;j<arrayI2.length;j++){
				System.out.println(arrayI2[j]+" ");
			}
			for(i=0;i<arrayI1.length;i++){
				System.out.println(arrayI1[i]+" ");
			}
		
		}
	}
}

public static void main(String[] args) {
    	String[] arrayI1 = new String[]{"abcd","abc"};
    	String[] arrayI2 = new String[]{"abd","bcd","adc"};
        Ordinamento.ordinamento1(arrayI1, arrayI2);

quello che mi stampa è molto diverso da quello che io vorrei:
2
abd
abd
abcd
abcd
abcd

qualcuno mi può dare una mano,grazie!!

[simo7784]

Ciao,ti propongo un approccio + a oggetti.
Ti scrivi una classe MSC che accetta come parametri due stringhe, nel costruttore memorizza le stringhe in variabili d'istanza, calcola la lunghezza della sottostringa comune alle due stringhe e memorizza anch'essa. L'interfaccia estendera' Comparable, sovrascrivi il metodo compareTo e fai in modo che l'ordinamento avvenga in base al valore della lunghezza, ma in ordine decrescente(se cerchi in post precedenti trovi un po' di esempi su come rendere oggetti comparabili). Metti tutti gli elementi in un array e riordini con Arrays.sort(tuoArray);
Ora hai un array ordinato, prendi il primo elemento e metti le due stringhe nei due array finali, prendi il secondo e, se le stringhe non sono ancora state inserite, inserisci anche queste. Cosi via fino a fine algoritmo.

[frankyster]

mhhhh!!ho capito quello che mi proponi,ma mi sarebbe utile se potresti scrivermi qualche riga di codice per focalizzare i punti cruciali da cui partire!!
per adesso ho fatto questootrebbe andare??

public abstract class Msc implements Comparable{
		private String I1;
		private String I2;
		
		public Msc(String I1,String I2){
			this.I1=I1;
			this.I2=I2;
		}
		public String getStringaI1(){
			return I1;
		}
		public String getStringaI2(){
			return I2;
		}
		public int lunghezza(){
			return longestCommonSubstring(I1,I2);
		}
		public int compareTo(Msc obj){
			Integer lunghezza=lunghezza();
			return lunghezza.compareTo(obj.lunghezza());
		}
		public static int longestCommonSubstring(String str1, String str2){
			
			if((str1==null && str1.length()==0) || (str2==null && str2.length()==0))
	            return 0;
	        int[][] num = new int[str1.length()][ str2.length()];
	        int maxlen = 0;
	        
	        for (int i = 0; i < str1.length();i++){
			   for (int j = 0; j < str2.length(); j++){
				   if (str1.charAt(i) != str2.charAt(j))
	                            num[i][ j] = 0;
	                            else{
									if ((i == 0) || (j == 0))
	                                    num[i][ j] = 1;
	                                    else
	                                    num[i][ j] = 1 + num[i - 1][ j - 1];

	                                    if (num[i][ j] > maxlen){
											maxlen = num[i][j];
	                                      
	                                    }
								}
	          }
	      }
	      return maxlen;
		}
	
	
	}

ma adesso??:master:

[simo7784]

allora la classe non abstract perche' dev'essere istanziabile.
Io metterei una variabile privata di tipo Integer lunghezza e nel costruttore la porrei uguale al risultato del metodo che ti calcola la lunghezza (metodo che non ti serve di definire statico in quanto stai istanziando un oggetto). Quindi

public class Msc implements Comparable{
		private String I1;
		private String I2;
                private Integer lunghezza;
		
		public Msc(String I1,String I2){
			this.I1=I1;
			this.I2=I2;
                        lunghezza = new Integer(longestCommonSubstring(I1,I2));
		}
		public String getStringaI1(){
			return I1;
		}
		public String getStringaI2(){
			return I2;
		}
		public Integer getLunghezza(){
			return lunghezza;
		}
                public int compareTo(Object obj){
                        Msc oggetto = (Msc)obj;
			return lunghezza.compareTo(obj.getLunghezza);
		}

		public int longestCommonSubstring(String str1, String str2){
			
			if((str1==null && str1.length()==0) || (str2==null && str2.length()==0))
	            return 0;
	        int[][] num = new int[str1.length()][ str2.length()];
	        int maxlen = 0;
	        
	        for (int i = 0; i < str1.length();i++){
			   for (int j = 0; j < str2.length(); j++){
				   if (str1.charAt(i) != str2.charAt(j))
	                            num[i][ j] = 0;
	                            else{
									if ((i == 0) || (j == 0))
	                                    num[i][ j] = 1;
	                                    else
	                                    num[i][ j] = 1 + num[i - 1][ j - 1];

	                                    if (num[i][ j] > maxlen){
											maxlen = num[i][j];
	                                      
	                                    }
								}
	          }
	      }
	      return maxlen;
		}
	}

Non ho controllato il metodo longestCommonSubstring ma hai detto che funziona.
A questo punto nella tua main class, crei un array che ha per lunghezza le possibili coppie e ci inserisci gli oggetti Msc istanziati con le possibili coppie. Alla riga dopo fai

Arrays.sort(tuoArray);

E l'array sara' ordinato come serve a te.
P.s. La classe Arrays va importata dal package java.util

[frankyster]

scusa simo ma non riesco proprio a implementarlo..mi dai una mano??

[simo7784]

Piu' o meno deve fare le cose scritte nei commenti. Ti torna?

import java.util.*;

public class Ordinamento {
   public static void Ordinamento1(String[]I1,String[]I2) {
      int dimensioni = I1*I2;
      //Creo un array temporaneo tuoArray di tipo Msc[dimensioni]
      int indice = 0;
      for(i che va da 0 a I1.length) {
         for(j che va da 0 a I2.length) {
            Msc tmpObject = new Msc(I1[i], I2[j]);
            //Inserisci l'oggetto nell'array che hai creato all'inizio
            //Incrementa l'indice
         }
      }
      Arrays.sort(tuoArray);
      String [] arrayI1= new String [I1.length];
      String [] arrayI2= new String [I2.length];
      for(i che va da 0 a tuoArray.length) {
         //Prendi l'oggetto Msc 
         //attraverso i metodi get ottieni le due stringhe
         //controlli che non siano gia' presenti
         //Se non presenti inserisci
      }
      //Eccetra eccetra
   }
}

P.s. C'era un mini errore nel compareTo() che ti avevo postato

    public int compareTo(Object obj){
        Msc oggetto = (Msc)obj;
        return lunghezza.compareTo(oggetto.getLunghezza());
    }

[frankyster]

adesso è tutto più chiaro,ero riuscito quasi a farlo..!!l'errore nel compareTo l'avevo gia corretto...adesso provo a implementare quello che manca..,grazie

[frankyster]

allora questo quello che ho fatto:che non va a buon fine,non termina mai l'applicazione!!

public class Ordinamento {
		public static void Ordinamento1(String[]I1,String[]I2) {
	      int dimensioni = I1.length*I2.length;
	      int i,j;
	      //Creo un array temporaneo tuoArray di tipo Msc[dimensioni]
	      Msc [] tmpArray = new Msc [dimensioni];
	      int indice = 0;
	      for(i=0;i<I1.length;i++) {
	         for(j=0;j<I2.length;j++) {
	             Msc tmpObject = new Msc(I1[i], I2[j]);
	             tmpArray[indice]=tmpObject;
	             indice++;
	            //Inserisci l'oggetto nell'array che hai creato all'inizio
	            //Incrementa l'indice
	         }
	      }
	      Arrays.sort(tmpArray);
	      String [] arrayI1= new String [I1.length];
	      String [] arrayI2= new String [I2.length];
	      for(i=0;i<tmpArray.length;i++){
	    	 Msc oggetto= tmpArray[i];
	    	 String stringaI1=oggetto.getStringaI1();
	    	 String stringaI2=oggetto.getStringaI2();
	    	 int h=0;
	    	 for(i=0;i<I1.length;i++){
	    		 if(!uguali(I1[i],stringaI1))
	    			 arrayI1[h]=stringaI1;
	    		     h++;
	    	 }
	    	 int g=0;
	    	 for(j=0;j<I2.length;j++){
	    		 if(!uguali(I2[j],stringaI2));
	    			 arrayI2[g]=stringaI2;
	    		     g++;
	    	 }
	      }
	      for(i=0;i<I1.length;i++){
	    	  System.out.println(I1[i]+" ");
	      }
	      for(i=0;i<I2.length;i++){
	    	  System.out.println(I2[i]+" ");
	      }
	   }
		
		public static boolean uguali(String a,String b){
			boolean uguali;
			if(a.length()== b.length()) {
				uguali = true;
				int i = 0;
				while(uguali && i<a.length()) {
					if(a.charAt(i) != b.charAt(i))
						uguali = false;
					    i = i+1;
			    }
			}
			else /*se t hanno lunghezza diversa, quindi sono diverse */
			uguali = false;
			return uguali;
		}
	}

public static void main(String[] args) {
    	String[] arrayI1 = new String[]{"abcd","abc"};
    	String[] arrayI2 = new String[]{"abd","bcd","adc"};
        Ordinamento.ordinamento1(arrayI1, arrayI2);

consigli!! :master:

[simo7784]

for(i=0;i<tmpArray.length;i++){
	    	 Msc oggetto= tmpArray[i];
	    	 String stringaI1=oggetto.getStringaI1();
	    	 String stringaI2=oggetto.getStringaI2();
	    	 int h=0;
	    	 for(i=0;i<I1.length;i++){
	    		 if(!uguali(I1[i],stringaI1))
	    			 arrayI1[h]=stringaI1;
	    		     h++;
	    	 }

Consigli? Un po' d'attenzione sui cicli...
Non puoi usare la stessa variabile per due for annidati perche'
1)perdi l'indice del for esterno
2)In casi come questo in cui il for interno termina con i che ha un valore < della guardia del for esterno, il programma va in loop.

Quella h poi non ti serve a niente, anzi fa casino. Riflettici su.

[frankyster]

ok ,ho modificato...e ho corretto anche le stampe..ma non è ordinato come vorrei...non viene considerata la coppia MSC(j21,j32)=1 oppure Msc(j11,j32) ma viene inserita la coppia(j21,j22)=2 in prima posizione ,le altre coppie (j11,j12) e infine j22 vengono inserite correttamente!!

public class Ordinamento {
		public static void Ordinamento1(String[]I1,String[]I2) {
	      int dimensioni = I1.length*I2.length;
	      int i,j;
	      //Creo un array temporaneo tuoArray di tipo Msc[dimensioni]
	      Msc [] tmpArray = new Msc [dimensioni];
	      int indice = 0;
	      for(i=0;i<I1.length;i++) {
	         for(j=0;j<I2.length;j++) {
	             Msc tmpObject = new Msc(I1[i], I2[j]);
	             tmpArray[indice]=tmpObject;
	             indice++;
	            //Inserisci l'oggetto nell'array che hai creato all'inizio
	            //Incrementa l'indice
	         }
	      }
	      Arrays.sort(tmpArray);
	      String [] arrayI1= new String [I1.length];
	      String [] arrayI2= new String [I2.length];
	      for(int indicetmp=0;indicetmp<tmpArray.length;indicetmp++){
	    	 Msc oggetto= tmpArray[indicetmp];
	    	 String stringaI1=oggetto.getStringaI1();
	    	 String stringaI2=oggetto.getStringaI2();
	    	 int h=0;
	    	 for(i=0;i<I1.length;i++){
	    		 if(!uguali(I1[i],stringaI1))
	    			 arrayI1[h]=stringaI1;
	    		     h++;
	    	 }
	    	 int g=0;
	    	 for(j=0;j<I2.length;j++){
	    		 if(!uguali(I2[j],stringaI2))
	    			 arrayI2[g]=stringaI2;
	    		     g++;
	    	 }
	    	
	      }
	      System.out.print("I1=");
	      for(i=0;i<arrayI1.length;i++){
	    	  System.out.print(arrayI1[i]+" ");
	      }
	      System.out.println();
	      System.out.print("I2=");
	      for(i=0;i<arrayI2.length;i++){
	    	  System.out.print(arrayI2[i]+" ");
	      }
	   }

stampa:
I1=abc abcd
I2=bcd abd bcd (la prima coppia non coincide con il risultato aspettato)