Buchstaben verdrehen (komplett und inkomplett) [und wieder Klartext]

Java-Forum Java-Grundlagen
1

Hi,

ich möchte Buchstaben verdrehen und hab’ mir gedacht (SSCCE):

        int newIdx = idx + 1;
        if (newIdx >= str.length()) {
            if (!set.contains(str)) {
                set.add(str);
            }
        } else {
            verdrehen(str, newIdx, set);
            verdrehen(str.substring(0, idx) + str.charAt(newIdx) + str.charAt(idx) + str.substring(newIdx + 2), newIdx, set);
        }
        return set;
    }```

(rekursive Funktion/Methode)

Die Ausgabe sollte sein [z. Bleistift]:

`[allHo, alloH, Hlloa, Hlalo, Halol, alHol, aHlol, Hallo, aHllo, Hlaol, Hllao, alHlo]`

leider bekomme ich 1) eine AIooBE. 2) Was lässt sich schneller machen?

3) Wie bestimme/ermittle ich, wie weit ein Wort mit verdrehten Buchstaben von dem Originalwort abweicht [4) in Prozent]?

Danke für de Müh'. Grüße.

Edit: Bei n Buchstaben in einem Wort, wobei alle Buchstaben unterschiedlich it, gibt es 2^(n-1) oder (2^n)/2 Möglichkeiten, was aber, wenn 5) ein Buchstabe doppelt oder sogar dreifach [6) nebeneinander] vorkommt?
2
  1. Im else ist newIdx < str.length und du rufst
str.substring(newIdx + 2)

auf.
2) Dauert es dir zu lange, bis die Exception fliegt? Spar dir das Mikrooptimieren.
3) z.B. Buchstaben durchiterieren und dann identische Buchstaben / Wortlänge.
4) Prozentrechnung.
5)/6) Wenn dien Drehen alle Möglichkeiten durchgehen soll: Anzahl Permutationen von X Elementen, wovon Y Elemente identisch sind.

3

Moin, mir ist was aufgefallen, was mir gestern nicht aufgefallen ist. Wenn der erste Buchstabe bis i durch getauscht wird, dann kann sich die Stellung der Buchstaben von i+1 bis n zwar noch ändern, aber nicht die Buchstaben von 1 bis i-1, damit gar nicht alle Permutationen. Zur anderen Sache, wenn alle Buchstaben um 1 verschoben sind, ist die Abweichung doch nicht so hoch, wie 1(oder 0) / n.

4

Edit: so gering, gibt es, durchgetauscht, etwas, -.-

5

[QUOTE=CyborgBeta]
Edit: Bei n Buchstaben in einem Wort, wobei alle Buchstaben unterschiedlich it, gibt es 2^(n-1) oder (2^n)/2 Möglichkeiten, was aber, wenn 5) ein Buchstabe doppelt oder sogar dreifach [6) nebeneinander] vorkommt?[/QUOTE]

Google MISSISSIPPI und Kombinatorik

6
7

Ja, das meinte ich. Also muss ich die nxm-Matrix durchgehen und je auf 3 Operationen testen? (n Länge Eingabe, m Länge Sollwort)

Wie kommt man an die möglichen Kandidaten für ein falschgeschriebenes Wort? (Also wie wählt man diese aus einer Array/List/Map/Set [sortiert, unsortiert, kleinste/größte oben/vorne usw.]?)

Und kann ich, wenn ich oben zwei benachbarte Zeichen-Elemente vertauscht habe, auch zurück, anstatt vor gehen (3 rekursive Aufrufe)?

Irgendwie ist dieses Thema schon spannend oder ned?

Grüße und Danke schon mal alle Kommentare

*** Edit ***

Oh, ich bin doch nicht doof/mad, ich hab’ einfach eine Zeile hinzugefügt, wer etwas damit anfangen kann:

        int newIdx = idx + 1;
        if (newIdx >= str.length()) {
            if (!set.contains(str)) {
                set.add(str);
                verdrehen(str, 0, set);
            }
        } else {
            verdrehen(str, newIdx, set);
            verdrehen(str.substring(0, idx) + str.charAt(newIdx) + str.charAt(idx) + str.substring(newIdx + 1), newIdx, set);
        }
        return set;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        System.out.println(verdrehen("Hallo", 0, new HashSet<String>()));
        System.out.println(verdrehen("Hallo", 0, new TreeSet<String>())); }```


Ausgabe
[spoiler]

run:
[lHloa, oHlal, olHal, Holal, oHlla, llHoa, ollaH, laHol, Hlola, aollH, alloH, loHal, alHol, llaHo, lloHa, Hloal, Hlaol, lHaol, allHo, laHlo, olalH, llaoH, oallH, aolHl, aHlol, oHall, lHlao, lHola, Hlloa, ollHa, Haoll, Holla, lHoal, oalHl, alHlo, oaHll, laloH, alolH, Hlalo, llHao, olHla, Hallo, loHla, aHllo, laolH, lloaH, loaHl, olaHl, loalH, laoHl, lolaH, Halol, lolHa, aoHll, lHalo, lalHo, aHoll, aloHl, Hoall, Hllao]
[Hallo, Halol, Haoll, Hlalo, Hlaol, Hllao, Hlloa, Hloal, Hlola, Hoall, Holal, Holla, aHllo, aHlol, aHoll, alHlo, alHol, allHo, alloH, aloHl, alolH, aoHll, aolHl, aollH, lHalo, lHaol, lHlao, lHloa, lHoal, lHola, laHlo, laHol, lalHo, laloH, laoHl, laolH, llHao, llHoa, llaHo, llaoH, lloHa, lloaH, loHal, loHla, loaHl, loalH, lolHa, lolaH, oHall, oHlal, oHlla, oaHll, oalHl, oallH, olHal, olHla, olaHl, olalH, ollHa, ollaH]
BUILD SUCCESSFUL (total time: 4 seconds)

[/spoiler]


Zu importieren sind: `import java.util.*;`

Die Idee ist ,wieder von vorne anzufangen (wenn sich Zeichen in der Zeichenkette geändert haben, es ein neues Teilergebnis gibt), und warum?, damit sich Buchstaben links nach dem ersten nach re verschobenen Buchstaben auch noch verschieben können.

Btw.: Der Einfachheit halber hat die Methode einen Rückgabetyp, ansammelnden Parameter und jeder Methodenaufruf die gleiche Rückgabe.

Erklärt mir trotzdem jemand das mit der nxm-Matrix (Levenshtein [nicht rekursiv])?
8

Kannst du vielleicht mal in einfachen Worten erklären, was genau du hier machst?

9

Einmal alle Permutation en ohne Schleife / einfach-rekursiv, zum anderen die Abweichung eines Worts von dem Originalwort, also wie wird Levenshtein imt der Matrix implementiert?.

10

Alle Permutationen eines Strings rekursiv erzeugen: OK

Levenshtein-Distanz zweier Strings berechnen: OK

Aber Matrix…wo ist da eine Matrix?