Gyakorlati alapok

Karakterpermutáció

 

Folytassuk tovább a kombinatorika felfedezését és implementációit!

 

Az alábbi NEM saját, futtatható Java-kód kiszámítja bármilyen begépelt szó összes karakterének összes, ismétlés nélküli permutációját. Például:

 

ABC

ACB

BAC

BCA

CAB

CBA

 

Mivel a kód nem azonosítja be és nem is validálja külön-külön a karaktereket, természetesen a kód hamar ismétléses permutáció-jellegűvé alakítható, ha egy karaktert többször is beütünk, például:

 

AAC

ACA

AAC

ACA

CAA

CAA

 

Ez azonban valójában nem ismétléses permutáció (ezért állítottuk, hogy csak "jellegű"), hiszen ebben a kódban minden kombináció formailag kétszer fordul elő, azaz kétszeresen redundáns, például:

 

AAC

ACA

AAC

ACA

CAA

CAA

 

Ezt további kódmódosítással ki lehetne küszöbölni, ám erre nem kaptunk felhatalmazást a szerzőtől, aki a javahungry.blogspot.com.

 

Az alkalmazásnak én a karakterpermutáció nevet adtam, hiszen bármilyen karakterkombinációt képes feldolgozni, ez lehet alapjában véve értelmetlen, de akár értelmes szóvá összeálló karaktercsoport.

 

www.informatika-programozas.hu - Ezt most meg kell tanulni!

 

Az azonnali futtathatóság érdekében 1 helyen meg kellett változtatnom a kódot: class Permutation helyett class Main névre neveztem át az osztályt!    

 

Nézzük meg a javahungry.blogspot.com futtatható Java-kódját!

 

www.informatika-programozas.hu - Futtatható Java-kód!

 

 

 

 

 

 

 


import java.util.Scanner;

class Main { //eredeti: class Permutation
public static void main (String args[]){
{
    System.out.println("Please enter the string whose permutations we need to show ");
    Scanner in = new Scanner(System.in);
    String original=in.nextLine();
    System.out.println("");
    System.out.println("Results are :");
    System.out.println("");
    permute(original);
    }
}

public static void permute (String input){
    int inputLength = input.length();
    boolean[ ] used = new boolean[ inputLength ];
    StringBuffer outputString = new StringBuffer();
    char[ ] in = input.toCharArray( );
    doPermute ( in, outputString, used, inputLength, 0 );
}

public static void doPermute ( char[ ] in, StringBuffer outputString,boolean[ ] used, int inputLength, int level){
    if( level == inputLength) {
        System.out.println ( outputString.toString());
        return;
    }
    for( int i = 0; i < inputLength; ++i ){
        if( used[i] ) continue;
            outputString.append(in[i]);
            used[i] = true;
            doPermute( in, outputString, used, inputLength, level + 1 );
            used[i] = false;
            outputString.setLength(outputString.length() - 1 );
        }
    } 
}

 

Végeredmény (például):

ABC

ACB

BAC

BCA

CAB

CBA