[Java] Permutatie probleem

[Verwijderd]

Hey mensen, ik heb over internet gezocht, de search gebruikt, en vele uren zelf geprobeerd deze klote error te verhelpen. Maar goed:

Als ik een permutatie van het woord voet wil dan krijg ik dit:

$ ipi Permutatie
Geef het woord waarvan u de permutaties wilt zien
voet
Alle permutaties in alfabetische volgorde:
eotv
oetv
teov
veot

de bedoeling is natuurlijk dat ik alle permutaties krijg.

Mijn

code:

    void beginpermutatie(StringBuffer woord) {
        for (int i=0; i < woord.length(); i++) {
            StringBuffer copyWoord = new StringBuffer(woord);
            StringBuffer begin = new StringBuffer(copyWoord.substring(i, i+1));
            StringBuffer eind = copyWoord.deleteCharAt(i);
            permuteer(begin, eind);
        }
    }
            
    public void permuteer(StringBuffer begin, StringBuffer eind) {
        if (eind.length() <= 1) {
            StringBuffer permutatieBuffer = begin.append(eind);
            String permutatie = permutatieBuffer.toString();
            if (permutationArray.checkPermutatie(permutatie) == false) {
                permutationArray.voegToe(permutatie);
            }
        } else {
            for (int i=0; i < eind.length(); i++) {
                StringBuffer tempEind = eind;
                StringBuffer newBegin = begin.append(tempEind.charAt(i));
                StringBuffer newEind = tempEind.deleteCharAt(i);
                permuteer(newBegin, newEind);
            }
        }
    }

Nog wat aan de rommelige kant mjah. Na verschillende testjes (wat out.printjes her en der) blijkt dus dat hij in permuteer de else kant gewoonweg niet hoger dan i=0 komt (wat er dus voor zou moeten zorgen dat ie andere letters ook omwisselt per hoogte van de recursie). Nadat ie 1 permutatie heeft toegevoegd gaat ie dus terug naar beginpermutatie (diens for) zelf ipv de bedoeling: permuteer (diens for).

ik heb geprobeerd het ook als new object te laten verwijzen maar dan krijg ik antwoorden als etoeoveovoeo . Google levert niks op en ik vraag me af wat ervoor zorgt dat ie de andere for van permutatie skipt


Iemand?
Alvast bedankt.

[Soultaker]

Ten eerste: post Java code met [code=java] .. [/code] tags, dat leest heel wat fijner.

Ten tweede: kun je eens in pseudo-code uitleggen wat je vindt dat je code moet doen? Ik kan er zelf namelijk geen chocola van maken en dan kan ik wel zeggen: het is verkeerd, begin maar opnieuw (wat op zich een goed idee is), maar dan moet je natuurlijk wel bedenken hoe je het anders kunt doen.

Het genereren van permutaties moet kunnen met één for-lus en één eindconditie (if-statement).

Verwijderd schreef op dinsdag 28 augustus 2007 @ 14:57:
Nog wat aan de rommelige kant mjah. Na verschillende testjes (wat out.printjes her en der) blijkt dus dat hij in permuteer de else kant gewoonweg niet hoger dan i=0 komt (wat er dus voor zou moeten zorgen dat ie andere letters ook omwisselt per hoogte van de recursie). Nadat ie 1 permutatie heeft toegevoegd gaat ie dus terug naar beginpermutatie (diens for) zelf ipv de bedoeling: permuteer (diens for).

Met alle respect, maar dat lijkt me sterk. Als je zelf al vindt dat het een rommeltje is, is het tijd om je code te herschrijven.

[ Voor 39% gewijzigd door Soultaker op 28-08-2007 15:14 ]

[Verwijderd]

Heey, ook Vu-er? Dit leest wat lekkerder:

Java:

void beginpermutatie(StringBuffer woord) {
    for (int i=0; i < woord.length(); i++) {
        StringBuffer copyWoord = new StringBuffer(woord);
        StringBuffer begin = new StringBuffer(copyWoord.substring(i, i+1));
        StringBuffer eind = copyWoord.deleteCharAt(i);
        permuteer(begin, eind);
    }
}
        
public void permuteer(StringBuffer begin, StringBuffer eind) {
    if (eind.length() <= 1) {
        StringBuffer permutatieBuffer = begin.append(eind);
        String permutatie = permutatieBuffer.toString();
        if (permutationArray.checkPermutatie(permutatie) == false) {
            permutationArray.voegToe(permutatie);
        }
    } else {
        for (int i=0; i < eind.length(); i++) {
            StringBuffer tempEind = eind;
            StringBuffer newBegin = begin.append(tempEind.charAt(i));
            StringBuffer newEind = tempEind.deleteCharAt(i);
            permuteer(newBegin, newEind);
        }
    }
}

Ik zie dat je helemaal geen comments gebruikt? Zeker als je net begint met recursie, is het onmogelijk om geen fouten te maken als je niet heel goed bijhoudt wat er gebeurt in je functie.

Zie mijn recursie-code die ik vorig jaar heb geschreven (andere opdracht, en geen java, dus copy-pasten kan je helaas niet doen ).

Java:

void tekenBoom(int diepte, boolean rechts, double lengte, int maxDiepte, int hoek)
{
    boolean links       = !rechts;
    double      lengteLinks,
                lengteRechts;
    
    //Bereken nieuwe lengtes
    
    if(diepte >= maxDiepte)
    {
        // Teken laatste boom
    
        return;
    }
    
    if(links)
    {
        diepte++;
        
        //Teken stukje huidige linkerboom
        
        //Teken nieuwe linkerboom
        
        //Teken stukje huidige linkerboom
        
        //Teken nieuwe rechterboom
        
        //Teken stukje huidige linkerboom
    }
    
    if(rechts)
    {
        diepte++;
        
        //Teken stukje huidige rechterboom
                
        //Nieuwe rechterboom
        
        //Teken stukje huidige rechterboom
    
        //Nieuwe linkerboom
        
        //Teken stukje huidige rechterboom
    }
}

En wat de poster boven me zegt: opnieuw beginnen wil ook weleens helpen.

[Janoz]

In tegenstelling tot het String object is StringBuffer wel muteerbaar. Na de volgende regel

StringBuffer eind = copyWoord.deleteCharAt(i);

zijn eind en copyWoord hetzelfde object en missen ze allebei de letter op positie i.

[Verwijderd]

Soultaker schreef op dinsdag 28 augustus 2007 @ 15:12:
Ten eerste: post Java code met [code=java] .. [/code] tags, dat leest heel wat fijner.

Ten tweede: kun je eens in pseudo-code uitleggen wat je vindt dat je code moet doen? Ik kan er zelf namelijk geen chocola van maken en dan kan ik wel zeggen: het is verkeerd, begin maar opnieuw (wat op zich een goed idee is), maar dan moet je natuurlijk wel bedenken hoe je het anders kunt doen.

Het genereren van permutaties moet kunnen met één for-lus en één eindconditie (if-statement).


[...]

Met alle respect, maar dat lijkt me sterk. Als je zelf al vindt dat het een rommeltje is, is het tijd om je code te herschrijven.

Ik heb meerdere malen geprobeerd de code te herschrijven maar ik kom telkens op iets vergelijkbaar met wat ik nu heb


Ik heb ff de comments erbij gezet:
Ik heb overigens in beginpermutatie copyWoord vervangen door eind, aangezien hij in principe hetzelfde is. Op deze manier wordt eind gewoon het hele woord en splitst hij deze langzamerhand in 2en.

Java:

    void beginpermutatie(StringBuffer woord) {
        // Krijgt een woord binnen dat vervolgens omgezet moet worden
        // B.v. abcd == woord dan wordt permuteer:
        // i=0: a+bcd, i=1: b+acd, i=2: c+abd, i=3: d+abc

        for (int i=0; i < woord.length(); i++) {
            StringBuffer eind = new StringBuffer(woord);
            StringBuffer begin = new StringBuffer(eind.substring(i, i+1));
            // ik heb met substring & StringBuffer gedaan omdat het via
            // eind.charAt(i) incompatible oplevert & andere
            // oplossingen geen andere mogelijkheden leverde.

            eind.deleteCharAt(i); 
            permuteer(begin, eind);
        }
    }
            
    public void permuteer(StringBuffer begin, StringBuffer eind) {
        if (eind.length() <= 1) {
            // indien er nog maar 1 letter uit te kiezen is van eind.
            // dan wordt het samengevoegd met begin en toegevoegd als hij
            // nog niet eerder is toegevoegd (zodat dubbelen worden vermeden)

            StringBuffer permutatieBuffer = begin.append(eind);
            String permutatie = permutatieBuffer.toString();
            if (permutationArray.checkPermutatie(permutatie) == false) {
                permutationArray.voegToe(permutatie);
            }
        } else {
            // in het andere geval, dus meer dan 1 letter in eind
            // wordt recursief 1 letter op plaats i in eind toegevoegd aan begin
            // en verwijdert uit de eind.

            for (int i=0; i < eind.length(); i++) {
                StringBuffer tempEind = eind;
                StringBuffer newBegin = begin.append(tempEind.charAt(i));
                StringBuffer newEind = tempEind.deleteCharAt(i);
                permuteer(newBegin, newEind);
            }
        }
    }

Janoz schreef op dinsdag 28 augustus 2007 @ 15:17:
In tegenstelling tot het String object is StringBuffer wel muteerbaar. Na de volgende regel

StringBuffer eind = copyWoord.deleteCharAt(i);

zijn eind en copyWoord hetzelfde object en missen ze allebei de letter op positie i.

Het probleem ligt niet aan beginpermutatie (zover ik heb gemerkt) maar misschien dat je iets anders bedoelde? Het is namelijk de bedoeling dat eind dat mee wordt gegeven de letter die hij in begin heeft gedropt wordt verwijderd. Bij elke for maakt hij een nieuw woord object aan (waardoor hij dus toch nog 4 keer de for runt, anders liep het al helemaal niet)

Probleem is dat hij bij methode permuteer niet verder dan i=0 komt bij alle aanroepen. Wellicht dat het if gedeelte van permuteer verhoedt dat hij vervolgens correct terug gaat naar de for in de recursie. Of dat een stringbuffer variabele niet helemaal goed runt.


Eventueel zou het ik kunnen proberen in string ipv stringbuffer aangezien hij nu nog weinig echt gebruik maakt van stringbuffer exclusieve truken.

[ Voor 20% gewijzigd door Verwijderd op 28-08-2007 15:59 ]

[Janoz]

Ik heb 1 regel uit je code gepakt en verteld wat het daadwerkelijk doet en ik vermoed dat dat iets anders is dan dat jij denkt dat het doet. Diezelfde 'fout' treed ook op in regel 24, 35, 36 en 37 van de hierboven geposte code.

[reddevil]

google doet ook wonderen voor een permutatie algoritme:
http://www.google.nl/sear...ermutation+algoritm&meta=

Code geleend van: http://www.thescripts.com/forum/thread629830.html
En beetje aangepast dat ie werkt in 1 file

Java:

interface Sortable {
    int length();
    int compare(int i, int j);
    void swap(int i, int j);
}

public class MySortable implements Sortable
{
    private String[] array;

    private MySortable(String[] array) { this.array = array; }

    public int length() {  // interface implementation

        return array.length;
    }

    public int compare(int i, int j)  { // interface implementation

        return array[i].compareTo(array[j]);
    }

    public void swap(int i, int j) { // interface implementation

        String t= array[i];
        array[i]= array[j];
        array[j]= t;
    }

    public void print() {

        for (int i= 0; i < array.length; i++)
            System.out.print(array[i]+" ");
        System.out.println();
    }

    public Sortable permute() {
        int i, j;

                // step 1
                for (i= length()-1; --i >= 0;)
                     if (compare(i, i+1) < 0)
                         break;

                if (i < 0) return null;

                // step 2
                for (j= length(); --j > i;)
                    if (compare(i, j) < 0)
                        break;

                // step 3
                swap(i, j);

                // step 4
                for (j= length(); ++i < --j;)
                    swap(i, j);

        return this;
    }

    public static void main(String[] args) {

        MySortable s= new MySortable(new String[] {
                        "a",
                        "b",
                        "c" });
        do {
            s.print();
        }
        while (s.permute() != null);
    }
}

[Verwijderd]

reddevil schreef op dinsdag 28 augustus 2007 @ 16:13:
google doet ook wonderen voor een permutatie algoritme:
http://www.google.nl/sear...ermutation+algoritm&meta=

Code geleend van: http://www.thescripts.com/forum/thread629830.html
En beetje aangepast dat ie werkt in 1 file

Java:

interface Sortable {
    int length();
    int compare(int i, int j);
    - knip-
}

Je realiseert je dat dit heel anders is geschreven vergeleken met mijn permutation programma?

Janoz schreef op dinsdag 28 augustus 2007 @ 16:12:
Ik heb 1 regel uit je code gepakt en verteld wat het daadwerkelijk doet en ik vermoed dat dat iets anders is dan dat jij denkt dat het doet. Diezelfde 'fout' treed ook op in regel 24, 35, 36 en 37 van de hierboven geposte code.

Om heel eerlijk te zijn zie ik niet echt wat dan precies de werking ervan is?

Uit de vorige code & comment:
StringBuffer eind = copyWoord.deleteCharAt(i);
zijn eind en copyWoord hetzelfde object en missen ze allebei de letter op positie i.


copyWoord wordt zelf telkens in de for een new object van Woord toen, waardoor het niet strijdt met de verloop van nieuwe woorden. In de permuteer als ik een new object zou maken van wat ie doorkrijgt krijg ik permutaties als voetoeveoveo terug


Ik heb net geprobeerd ipv StringBuffer String te gebruiken en die werkt in 1 keer helemaal goed
Maar dan rest me nog enigszins de vraag waarom het via StringBuffer niet verloopt

[ Voor 35% gewijzigd door Verwijderd op 28-08-2007 16:24 ]

[Janoz]

Neem bijvoorbeeld regel 24

StringBuffer permutatieBuffer = begin.append(eind);

Gaan we er van uit dat begin =abc en eind=def

Deze regel zorgt ervoor dat aan begin eind wordt geplakt. Begin bevat nu dus 'abcdef'. Daarna gaat permutatieBuffer naar hetzelfde object verwijzen.

Aan het einde heb je dus nog steeds twee objecten. De ene heeft def en hiernaar verwijst eind en het andere object bevat abcdef en hiernaar verwijzen permutatieBuffer en begin. Het is dus niet zo dat begin nog steeds abc bevat en het is ook niet zo dat begin en permutaiteBuffer twee verschillende dingen zijn.

Zet tussen elke regel eens

Java:

System.out.println("Begin  = "+ begin.toString);
System.out.println("Eind  = "+ eind.toString);
System.out.println("Buffer  = "+ permutatieBuffer.toString);

en zie wat er gebeurt en vergelijk dit met dat je zou verwachten dat er zou gebeuren. Wat je ook kunt doen is even de debugger pakken en door je code heen steppen.

-----

nav edit: Dat komt dus omdat strings immutabel zijn. Een string is niet te veranderen. Bij een bewerking wordt de veranderde waarde terug gegeven terwijl een stringbuffer de verandering toepast op zichzelf.


Waarom levert een aanroep op de aanpassingsmethode dan een StringBuffer op?

Dat zit (afaik) ook in enkele andere OO talen en maakt het makkelijk om veel bewerkingen achter elkaar te zetten. Veel bewerkingen leveren stringbuffer op, maar dat is gewoon een reverentie naar zichzelf. (er staat return this; aan het einde). Hierdoor kun je dingen doen als:

new StringBuffer("aap,").append("noot,").append("mies");

[ Voor 24% gewijzigd door Janoz op 28-08-2007 16:37 ]

[Verwijderd]

Excuus voor late reactie, van alles en nog wat vliegt om me oren. Hoe dan ook: hartstikke bedankt allemaal voor jullie reacties!