Visualizzazione dei risultati da 1 a 10 su 10
  1. #1

    permutazioni

    Ciao ragazzi, sto cercando di scrivere un metodo che mi restituisca
    tutte le permutazioni di una frase es:
    "il mio gatto"
    "il gatto mio"
    "mio gatto il"
    "mio il gatto"
    "gatto il mio"
    "gatto mio il"

    la signature del metodo dovrebbe essere cosi:
    codice:
    public String[] permutate(String str){
            String[]  tmpStr = null; 
            StringTokenizer tok = new StringTokenizer(str);
            int countToken = tok.countTokens();
            tmpStr = new String[countToken];
    
            for (int i = 0; i < countToken; i++){
                tmpStr[i] = tok.nextToken();
                
            }
    }
    Il corpo del metodo intanto suddivide in token la frase e salva
    ogni parola in un array di stringhe per le elaborazioni.
    Accetto sia soluzioni ricorsive che iterative...
    Grazie per l'aiuto
    Nulla, ma e' sempre qualcosa.

  2. #2
    Utente di HTML.it
    Registrato dal
    Feb 2004
    Messaggi
    724
    su di un vettore. Puoi fare le permutazioni sugli indici e poi stampare il contenuto dell'indice
    codice:
    public class Permutazioni
    {
        public static void generaPermutazioni(int[] B, int estremoinferiore)
        {   int temp;
    	// stampa permutazione attuale
    	if (estremoinferiore==B.length-1) {
    	for (int j=0; j<B.length; j++) System.out.print(B[j]+" ");
    	System.out.println();
        }
    	for (int i=estremoinferiore; i<B.length; i++)
    	  {temp = B[estremoinferiore];
    	   B[estremoinferiore] = B[i];
    	   B[i] = temp;
    	   generaPermutazioni(B, estremoinferiore+1);
    	   temp = B[estremoinferiore];
    	   B[estremoinferiore] = B[i];
    	   B[i] = temp;
    	}
        }
       
        public static void main()
        { int[] A = {4,3,2,1};
          generaPermutazioni(A,0);
    }
    }

    questo lo fa su di una stringa
    codice:
    public class Permutazioni {
    
      // stampa su un PrintStream tutte le permutazioni della stringa s
      public static void permutazioni(String s, PrintStream ps) {
        permutazioni("", s, ps);
      }
    
      private static void permutazioni(String fissa, String permuta,
                                       PrintStream ps) {
        if (permuta.length() == 0)
          ps.println(fissa);
        else
          for (int i = 0; i < permuta.length(); i++)
            permutazioni(fissa + permuta.charAt(i),
                         permuta.substring(0,i) + permuta.substring(i+1),
                         ps);
      }
    }

  3. #3
    Intanto grazie per l'interesse
    Lo scopo per cui sto cercando la permutazione di una stringa e' che sto
    utilizzando i canali della tecnologia nio per la scrittura e la lettura su file.
    Quindi ho bisogno che nell'ambiente chiamante il metodo mi restituisca
    la permutazione per la successiva scrittura su file.
    Riguardo l'array di interi ho risolto cosi':
    codice:
    package esercizi.ese_4;
    
    import java.io.PrintStream;
    import java.util.StringTokenizer;
    
    /**
     *
     * @author mau2
     */
    public class TryPermutation {    
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) {
            // TODO code application logic here
            
            int [] numbers = {1, 2, 3, 4};
            int [][] permutazioni;
            
            permutazioni = Permutazioni.permuta( numbers );
            
            for (int i = 0; i < permutazioni.length; i++) {
                for (int j = 0; j < permutazioni[i].length; j++) {
                    System.out.print(permutazioni[i][j] + " ");
                }
                System.out.println();
                
            }
            //scrittura dati su file...
            
            
        }
        
        public static class Permutazioni {
            static int [][] p;
            static int index = 0;
            public static int[][] permuta(int [] number){
                
                p = new int[factorial(number.length)][number.length];
                generaPermutazioni(number, 0);
                return p;
            }
            public static void generaPermutazioni(int[] B, int estremoinferiore) {
                int temp;
                
                // stampa permutazione attuale
                if (estremoinferiore == B.length-1) {
                    for (int j = 0; j < B.length; j++){
                        if(index == 24 )
                            break;
                        p[index][j] = B[j];
                    }
                    index++;
                }
                
                for (int i = estremoinferiore; i < B.length; i++) {
                    temp = B[estremoinferiore];
                    B[estremoinferiore] = B[i];
                    B[i] = temp;
                    generaPermutazioni(B, estremoinferiore + 1);
                    temp = B[estremoinferiore];
                    B[estremoinferiore] = B[i];
                    B[i] = temp;
                }
            }
            private static int factorial(int num){
                int count = 1;
                for (int i = 2; i <= num; i++) {
                    count *= i;
                }
                
                return count;
            }
        }
    }
    Riguardo i metodi che mi hai fornito per le stringhe non fa esattamente
    cio' che desidero...
    La permutazione deve essere fatta sulle parole della frase, infatti nel
    metodo template che ho fornito nel primo post scompone la frase in parole
    utilizzando il separatore di default di StringTokenizer() ovvero lo spazio
    cosi' dopo effettua la permutazioni sulle parole.
    Per esempio sulla stringa "il mio gatto" la permutazione e' la seguente:
    "il mio gatto"
    "il gatto mio"
    "mio gatto il"
    "mio il gatto"
    "gatto il mio"
    "gatto mio il"
    Cmq sul metodo da te fornito e' matematico che la permutazione da me cercate
    e' un sottoinsieme delle permutazioni che il tio metodo effettua.
    Rimangono 2 cose da fare una e' la restituzione, all'ambiente chiamante,
    delle permutazioni e l'altro cambiare l'algoritmo.
    Ora ci lavoro....
    Nulla, ma e' sempre qualcosa.

  4. #4
    Utente di HTML.it
    Registrato dal
    Feb 2004
    Messaggi
    724
    non ho ancora provato il codice nuovo che hai postato, però io farei una cosa del genere... Calcoli il numero di parole della frase, crei un nuovo vettore e lo popoli con tanti elementi quante solo le parole, effettui le permutazioni su questo vettore. per ogni ordine che ottieni prendi ogni singolo numero e stampi la parola corrispondente

  5. #5
    Bene ci intendiamo perfettamente!!!Cmq se vedi il primo post
    fa la scomposizione...
    Quindi come dici allora bisogna usare sempre lo stesso algoritmo
    utilizzato per gli interi!!
    Nulla, ma e' sempre qualcosa.

  6. #6
    E voila' ho trovato tutte le soluzioni!!:
    codice:
    package esercizi.ese_4;
    
    import java.io.PrintStream;
    import java.nio.Buffer;
    import java.util.StringTokenizer;
    
    /**
     *
     * @author mau2
     */
    public class TryPermutation {
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) {
            // TODO code application logic here
            
            int [] numbers = {1, 2, 3, 4};
            int [][] INTpermutazioni;        
            String[] STRpermutazioni;
            
            INTpermutazioni = PermutaInt.permuta( numbers );
            
            for (int i = 0; i < INTpermutazioni.length; i++) {
                for (int j = 0; j < INTpermutazioni[i].length; j++) {
                    System.out.print(INTpermutazioni[i][j] + " ");
                }
                System.out.println();
                
            }
            
            STRpermutazioni = PermutaPhrase.permuta("il mio gatto");
            //System.out.println(STRpermutazioni.length);
            for (int i = 0; i < STRpermutazioni.length; i++) {            
                    System.out.print(STRpermutazioni[i]);           
                System.out.println();
                
            }
            
            //scrittura dati su file...
        }
        
        private static class PermutaInt {
            static int [][] p;
            static int index = 0;
            public static int[][] permuta(int [] number){            
                p = new int[factorial(number.length)][number.length];
                generaPermutazioni(number, 0);
                return p;
            }
            public static void generaPermutazioni(int[] B, int estremoinferiore) {
                int temp;            
                // stampa permutazione attuale
                if (estremoinferiore == B.length-1) {
                    for (int j = 0; j < B.length; j++){
                        
                        p[index][j] = B[j];
                    }
                    index++;
                }            
                for (int i = estremoinferiore; i < B.length; i++) {
                    temp = B[estremoinferiore];
                    B[estremoinferiore] = B[i];
                    B[i] = temp;
                    generaPermutazioni(B, estremoinferiore + 1);
                    temp = B[estremoinferiore];
                    B[estremoinferiore] = B[i];
                    B[i] = temp;
                }
            }        
        }
        
        
        
        private static class PermutaPhrase{
            static String [] strReturned;
            static String [][] tmpStr;
            static int index = 0;
            public static String[] permuta(String str){
                StringTokenizer tok = new StringTokenizer(str);
                int countToken = tok.countTokens();
                tmpStr = new String[factorial(countToken)][countToken];
                
                //intanto popoliamo il primo indice dell'array bidimensionale
                //con la striga  str passata come argomento
                //anche se tale popolamento verra' sovrascritto serve per passare l'array
                //monodimenrionale al metodo generaPermutazioni
                for (int i = 0; i < countToken; i++){
                    tmpStr[0][i] = tok.nextToken();
                    
                }           
                
                generaPermutazioni(tmpStr[0], 0);
                
                //adesso popoliamo l'array monodimensionale con tutte le permutazioni           
                StringBuffer [] buffer = new StringBuffer[factorial(tmpStr[0].length)]; 
                strReturned = new String[factorial(tmpStr[0].length)];
                for (int i = 0; i < buffer.length; i++) {
                    buffer[i] = new StringBuffer();
                }
                for (int index = 0, i = 0; i < tmpStr.length; i++, index++) {
                    
                    for (int j = 0; j < tmpStr[i].length; j++) {                    
                        buffer[index].append(tmpStr[i][j] + " ");
                    }   
                    
                }            
                for (int i = 0; i < buffer.length; i++) {
                    strReturned[i] = buffer[i].toString();
                }
                
                
                return strReturned;
            }
            public static void generaPermutazioni(String[] B, int estremoinferiore) {
                String temp;
                
                // stampa permutazione attuale
                if (estremoinferiore == B.length-1) {
                    for (int j = 0; j < B.length; j++){
                        
                        tmpStr[index][j] = B[j];
                    }
                    index++;
                }
                
                for (int i = estremoinferiore; i < B.length; i++) {
                    temp = B[estremoinferiore];
                    B[estremoinferiore] = B[i];
                    B[i] = temp;
                    generaPermutazioni(B, estremoinferiore + 1);
                    temp = B[estremoinferiore];
                    B[estremoinferiore] = B[i];
                    B[i] = temp;
                }
            }
            
        }
        
        private static int factorial(int num){
            int count = 1;
            for (int i = 2; i <= num; i++) {
                count *= i;
            }
            
            return count;
        }
        
        
    }
    Nulla, ma e' sempre qualcosa.

  7. #7
    Utente di HTML.it
    Registrato dal
    Feb 2004
    Messaggi
    724
    questa versione è un po più compatta

    codice:
    import java.io.PrintStream;
    import java.util.*;
    import java.util.StringTokenizer;
        
    public class permutazioni
    {
    	static int ind=0;
    	public permutazioni(){
    		}
    	public static void permutate(){
    		String str="Ciao sono io";
            String[]  tmpStr = null; 
            StringTokenizer tok = new StringTokenizer(str);
            int countToken = tok.countTokens();
            tmpStr = new String[countToken];
    
            for (int i = 0; i < countToken; i++){
                tmpStr[i] = tok.nextToken();
                    }
           int lu= countToken;
       
          String[][]qw=new String[factorial(lu)][lu];
    	ArrayList a=new ArrayList();
    	String s="";
    	for(int i=0;i<=lu-1;i++){
    		s=Integer.toString(i+1);
    		a.add(s);
    	}
    	   int []B=new int[a.size()];
    	   	   for (int i=0;i<=B.length-1;i++){
    	   	B[i]=i;
    	   	}
    	generaPermutazioni(qw,tmpStr,B,0);
    	}
    	
    	    public static void generaPermutazioni(String[][]qw,String[]s,int[]B, int estremoinferiore)
    	    {   int temp;
    	    
    	   		// stampa permutazione attuale
    	    if (estremoinferiore==B.length-1) {
    			for (int j=0; j<B.length; j++){ 
    				qw[ind][j]=s[B[j]];
    				System.out.print(qw[ind][j]+" ");
    			}ind++;
    			System.out.println();
    		    }
    			for (int i=estremoinferiore; i<B.length; i++)
    			  {temp = B[estremoinferiore];
    			   B[estremoinferiore] = B[i];
    			   B[i] = temp;
    			   generaPermutazioni(qw,s,B, estremoinferiore+1);
    			   temp = B[estremoinferiore];
    			   B[estremoinferiore] = B[i];
    			   B[i] = temp;
    			}    }
    	    
    	    private static int factorial(int num){
    	        int count = 1;
    	        for (int i = 2; i <= num; i++) {
    	            count *= i;
    	        }
    	        
    	        return count;
    	    }
    
    	    public static void main(String[] _args)
        { permutate();
        }}
    manca solo la scrittura su file

  8. #8
    Si e' vero ma rimane sempre il fatto che nel main() devo scrivere le stringhe su file,
    cosi come l'hai progettato tu il metodo e' perfettamente funzionante ma mi restituisce
    void.
    Di seguito c'e' il main() che scrive i dati su file e puoi vedere come il metodo della classe
    che ho postato restituisce l'array di permutazioni.
    codice:
    public static void main(String[] args) {
             String[] STRpermutazioni;
            
            
            
            STRpermutazioni = PermutaPhrase.permuta("il mio gatto");
            
            File aFile = new File("C:/Beg Java Stuff/permutation.txt");
           OutChannel channel = new OutChannel(aFile, true, false);
            ByteBuffer byteBufer = ByteBuffer.allocateDirect(STRpermutazioni[0].length() + 1);
            
            for (int i = 0; i < STRpermutazioni.length; i++) {
                byteBufer.put((STRpermutazioni[i] + "\n").getBytes());
                byteBufer.flip();
                channel.write(byteBufer);
                byteBufer.clear();
            }
            System.out.println("File written is " + channel.size() + " bytes.");
            channel.close();
            
           
        }
    La classe OutChannel l'ho scritta per ridurre il codice attinente alla scrittura di dati
    sul file, quindi non ci fare caso ma te la posto lo stesso:
    codice:
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.nio.ByteBuffer;
    import java.nio.MappedByteBuffer;
    import java.nio.channels.ClosedChannelException;
    import java.nio.channels.FileChannel;
    import java.nio.channels.FileLock;
    import java.nio.channels.ReadableByteChannel;
    import java.nio.channels.WritableByteChannel;
    import javax.swing.JFileChooser;
    
    /**
     *
     * @author mau2
     */
    /*in questa classe bisogna includere altri costruttori
     *che prevedano l'apertura dello stream con gli altri costruttori
     *overloaded della classe FileOutputStream*/
    public class OutChannel{
        
        private FileOutputStream outStream;
        private FileChannel outChannel;
        private FileLock lock = null;
        private long position;
        private boolean random = false;
        /** Creates a new instance of ChannelUtility */
        public OutChannel(File file, boolean createDirectory, boolean append){
            
            if(createDirectory && !file.exists())
                createDir(file);
            try {
                outStream = new FileOutputStream(file, append);
            } catch (FileNotFoundException e) {
                e.printStackTrace(System.err);
            }
            
            outChannel = outStream.getChannel();
        }
        
        
        
        
        
        public int write(ByteBuffer buf){
            
            int tmp = buf.limit() - buf.position();
            
            try{
                if(random){
                    outChannel.write(buf, position);
                    position += tmp;
                }else
                    outChannel.write(buf);
                outChannel.force(true);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            
            return tmp;
            
        }
        
        public int write(ByteBuffer buf, long position){
            int size = -1;
            try {
                size = outChannel.write(buf, position);
                outChannel.force(true);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            
            return size;
        }
        
        public long write(ByteBuffer[] bufs){
            long size = -1;
            long tmp = 0;
            ByteBuffer tmpBuf = null;
            
            for (int i = 0; i < bufs.length; i++) {
                tmp += bufs[i].limit() - bufs[i].position();
            }
            tmpBuf = ByteBuffer.allocate((int)tmp);
            for (int i = 0; i < tmp; i++) {
                tmpBuf.put(bufs[i]);
            }
            tmpBuf.flip();
            try {
                if(random){
                    size = outChannel.write(tmpBuf, position);
                    position += tmp;
                    outChannel.force(true);
                }else
                    size = outChannel.write(tmpBuf);
                outChannel.force(true);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            
            return size;
        }
        
        public long write(ByteBuffer[] bufs, int offset, int length ){
            long size = -1;
            long tmp = 0;
            ByteBuffer tmpBuf = null;
            for (int i = offset; i < offset + length; i++) {
                tmp += bufs[i].limit() - bufs[i].position();
            }
            tmpBuf = ByteBuffer.allocate((int)tmp);
            for (int i = offset; i < offset + length; i++) {
                tmpBuf.put(bufs[i]);
            }
            tmpBuf.flip();
            
            try {
                if(random){
                    size = outChannel.write(tmpBuf, position);
                    position += tmp;
                }else
                    size = outChannel.write(tmpBuf);
                outChannel.force(true);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            
            return size;
        }
        
        public OutChannel position(long newPosition){
            position = newPosition;
            random = true;
            return this;
        }
        
        public long position(){
            long seek = -1;
            if(random){
                seek = position;
            } else{
                try {
                    seek = outChannel.position();
                } catch (IOException e) {
                    
                }
            }
            return seek;
        }
        
        
        
        public void append(){
            random = false;
            position = 0;
        }
        public boolean isRandom(){
            return random;
        }
        
        public void close(){
            try {
                outStream.close();
            } catch  (IOException e) {
                e.printStackTrace(System.err);
            }
            
        }
        
        public void force(){
            try {
                outChannel.force(true);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            
        }
        
        public long size() {
            long tmp = 0;
            try {
                tmp = outChannel.size();
            } catch (IOException e) {
                
            }
            return tmp;
        }
        
        
        
        public MappedByteBuffer map(FileChannel.MapMode mode, long position, long size){
            MappedByteBuffer buf = null;
            try {
                buf = outChannel.map(mode, position, size);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            return buf;
        }
        
        //questo metodo non l'ho completato perche' gia' presente sulla classe InChannel
        //in quanto piu' naturale nel codice
        private long transferFrom(ReadableByteChannel src, long position, long count) throws IOException {
            return -1;
        }
        
        
        
        
        public FileLock tryLock(long position, long size, boolean shared){
            
            try {
                lock = outChannel.tryLock(position, size, shared);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            return lock;
        }
        public FileLock tryLock(long position, long size){
            
            try {
                lock = outChannel.tryLock(position, size, false);
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            return lock;
        }
        public void tryLock(){
            
            try {
                lock = outChannel.tryLock();
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
            
        }
        
        public boolean isLocked(){
            if(lock == null)
                return false;
            else
                return true;
        }
        public void releaseLock(){
            try {
                lock.release();
            } catch (IOException e) {
                e.printStackTrace(System.err);
            }
        }
        
        
        public FileChannel getOriginalChannel() {
            return outChannel;
        }
        
        public boolean isOpen() {
            return outChannel.isOpen();
        }
        
        /**
         * 
         * @param file 
         */
        private void createDir(File file){
            File dir = new File(file.getParent());
            if (!dir.exists())                      // If directory does not exist
            {
                if (!dir.mkdir())                     // ...create it
                {
                    System.out.println("Cannot create directory: " + file);
                    System.exit(1);
                }
            } else if (!dir.isDirectory()) {
                System.err.println(file + " is not a directory");
                System.exit(1);
            }
        }
        
        public FileChannel truncate(long size) throws IOException {
            return null;
        }
        
        
        protected void implCloseChannel() throws IOException {
        }
        
        
        
        
        
        
        
        
        
        
    }
    Nulla, ma e' sempre qualcosa.

  9. #9
    Utente di HTML.it
    Registrato dal
    Feb 2004
    Messaggi
    724
    nn c'è nessun problema sostituisci void con il formato che ti serve e poi aggiungi in fondo alla funzione un return seguito dall'oggetto che ritorni.

  10. #10
    Ti ga' ragion
    Nulla, ma e' sempre qualcosa.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.