[ALG] Char swapping probleem

[Verwijderd]

Allereerst moet ik even zeggen dat ik niet precies weet in welke categorie ik dit moet posten, maar ik hoop het met wat programmeerwerk te kunnen oplossen. Ik zal het probleem toelichten met wat java code. Stel ik heb een String en wil deze op een simpele manier encrypten.

Java:

private void encrypt(String s)
{
   char ac[] = s.toCharArray();
        for(int j = 0; j < ac.length - 1; j++)
        if(ac[j] > ac[j + 1])
        {
            char c = ac[j];
            ac[j] = ac[j + 1];
            ac[j + 1] = c;
        }      

        return new String(ac);
    }

Als ik nu de String "koekje" versleutel krijg ik met deze methode "kekjeo". Wil ik nu "kekjeo" terugzetten naar het origineel dan doe ik het omgekeerde:

Java:

    private void decrypt(String s)
    {
        char ac[] = s.toCharArray();
        
        for(int j = ac.length - 1; j > 1; j--)
        {
            if(ac[j - 1] < ac[j])
            {
                char c = ac[j - 1];
                ac[j - 1] = ac[j];
                ac[j] = c;
            }
        }

        return new String(ac);
    }

Dit levert keurig weer koekje op...MAAR...er zijn meerdere manieren om "kekjeo" te krijgen na encryptie..zoals "okekje" en "kkeoje"....hoe vind ik deze 2 string terug? want als ik "kekjeo" decrypt met de decrypt methode dan vind ik nooit die andere 2. Iemand een idee hoe dit probleem op te lossen valt.

En een brute force met alle mogelijke string permutaties is geen optie, omdat de string in m'n echte geval langer is (14 chars)

[ Voor 54% gewijzigd door Verwijderd op 25-02-2006 21:43 ]

[H!GHGuY]

ff wat ik aant posten was verwijderd want ik snapte je opgave niet helemaal...

telkens je een swap uitvoert kun je deze WEL en NIET doen (de 2 tekens stonden in volgorde, of ze stonden niet in volgorde). Je legt dus een string-array aan met variabele grootte.
telkens je een teken kan wisselen voeg je zowel de string met wisselen als die zonder wisselen aan je array toe.

zodoende overloop je string-array telkens opnieuw voor het volgende teken.

code:

for (aantal_tekens - 1 naar 0)
   for (elke string in de array)
      als swap moet
         voeg_string_toe_met_swap
         voeg_string_toe_zonder_swap

zoiets dus.

stel dat in de gegeven string n swaps mogelijk zijn
dan hou je uiteindelijk maximaal 2^n strings over.