INF2220 ukeoppgaver uke 4
=========================



OPPGAVE 1:
----------

Dere skal l?se den f?rste oppgaven fra kompendium til Krogdahl og
Maus. (oppgaven under seksjon 16. plassering av 9 sifre).

Dere skal ikke l?se tilleggsoppgaven. Dere skal ta utgangspunkt
i kildekoden som ligger nederst i denne fila. Der har dere
en generisk rekursiv algoritme som genererer alle permutasjoner
av en tekststreng. Vi skal se p? permutasjoner av tekststrengen

123456789

og vi er kun interessert i permutasjoner som matcher kravet
som blir beskrevet i oppgaveteksten. Dere skal med andre ord
legge inn avskj?ringer som gj?r at vi ikke fortsetter ? kikke
p? tekstrenger som ikke tilfredstiller krav. dvs.

har vi kommet til et punkt der vi har generert strengen: 17
kan vi gi opp videre generering siden dette tallet ikke
er delelig med 2 osv.



OPPGAVE 2:
----------

L?s den samme oppgaven, men bruk rammeverket til Krogdahl og
Maus til ? generere permutasjoner, dvs. noe ala AvskjProg
side 8 kompendium.


=========================code==============================

public class Permutation{

    // use the entire string as the endingString
    // when called with one parameter
    public void permuteString(String s){
        permuteString("", s);
    }

    public void assignment1(){
        long t_0 = System.currentTimeMillis();

        permuteString("123456789");

        System.out.println("time used: "+(System.currentTimeMillis() - t_0)+" ms");
    }

    // recursive declaration of method permuteString
    public void permuteString(
            String beginningString, String endingString ){

        // base case: if string to permute is length less than or equal to
        // 1, just display this string concatenated with beginningString
        if ( endingString.length() <= 1 ){
            System.out.println( beginningString + endingString );
        }else{ // recursion step: permute endingString

            // for each character in endingString
            for ( int i = 0; i < endingString.length(); i++ ){
                try{
                    
                    // create new string to permute by eliminating the
                    // character at index i
                    String newEndString = endingString.substring( 0, i ) + endingString.substring( i + 1 );

                    String newBeginString = beginningString + endingString.charAt( i );

                    // recursive call with a new string to permute
                    // and a beginning string to concatenate, which
                    // includes the character at index i

                    permuteString( newBeginString, newEndString );

                }catch ( StringIndexOutOfBoundsException exception ){
                    exception.printStackTrace();
                }
            } 
        } 
    } 




    public static void main(String[] args){
        Permutation p = new Permutation();
        // try it out with your input arguments
        for(String s : args){
            p.permuteString(s);
            System.out.println("----------");
        }

        // uncomment next line and
        // solve the assignement
        // p.assignment1();
    }
}