Permutaatiot rekursiivisella funktiolla

Posted on by
Bookmark and Share

Tulipa kokeiltua permutaatioiden tekemistä javalla. Netistä ei löytynyt ihan suoraa ratkaisua Javalle, joten piti itse kehitellä.

PLAIN TEXT
JAVA:
  1. class Permutointi
  2. {
  3.     static int metodikutsuja = 0, permutaatioita = 0;
  4.  
  5.     public static void main(String[] args)
  6.     {
  7.         String merkkijono = "abcde";
  8.  
  9.         permutoi(merkkijono, "");
  10.  
  11.         System.out.println("Permutaatioita: " + permutaatioita);
  12.         System.out.println("Metodikutsuja: " + metodikutsuja);
  13.            
  14.     }
  15.    
  16.     static void permutoi(String jono, String alku)
  17.     {
  18.         String uusi_alku="", lyhyempi="";
  19.        
  20.         metodikutsuja++;
  21.        
  22.         if (jono.length() == 0)
  23.         {
  24.         }
  25.         else if (jono.length() == 1)
  26.         {
  27.             System.out.println(alku+""+jono.charAt(0));
  28.             permutaatioita++;
  29.         }
  30.         else if (jono.length() == 2)
  31.         {
  32.             System.out.println(alku+""+jono.charAt(0)+""+jono.charAt(1));
  33.             permutaatioita++;
  34.            
  35.             System.out.println(alku+""+jono.charAt(1)+""+jono.charAt(0));
  36.             permutaatioita++;
  37.         }
  38.         else
  39.         {
  40.             for (int i=0; i<jono.length(); i++)
  41.             {
  42.                 lyhyempi="";
  43.                 for (int j=0; j<jono.length(); j++)
  44.                 {
  45.                     if (j!=i)
  46.                         lyhyempi = lyhyempi + jono.charAt(j);
  47.                 }
  48.                
  49.                 uusi_alku = alku + jono.charAt(i);
  50.                 permutoi(lyhyempi, uusi_alku);
  51.             }
  52.         }
  53.     }
  54. }

abcde, eli 5 merkkiä aiheuttaa 86 metodikutsua ja permutaatioita löytyy (tietenkin) 5!=120 kappaletta.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>