java-string-Permutationen und Kombinationen-lookup

Schreibe ich eine Android word-app. Mein code enthält eine Methode finden würde, dass alle Kombinationen von Strings und Teilstrings eines 7 Buchstaben-Zeichenfolge mit mindestens der Länge 3. Dann vergleichen Sie alle verfügbaren Kombination zu jedem Wort im Wörterbuch zu finden, der alle gültigen Wörter. Ich bin mit einer rekursiven Methode. Hier ist der code.

//Gets all the permutations of a string.
void permuteString(String beginningString, String endingString) {
    if (endingString.length() <= 1){
        if((Arrays.binarySearch(mDictionary, beginningString.toLowerCase() +   endingString.toLowerCase())) >= 0){
            mWordSet.add(beginningString + endingString);
        }
    }
    else
        for (int i = 0; i < endingString.length(); i++) {
            String newString = endingString.substring(0, i) + endingString.substring(i + 1);
            permuteString(beginningString + endingString.charAt(i), newString);
      }
}
//Get the combinations of the sub-strings. Minimum 3 letter combinations
void subStrings(String s){
    String newString = "";
    if(s.length() > 3){
        for(int x = 0; x < s.length(); x++){
            newString = removeCharAt(x, s);
            permuteString("", newString);
            subStrings(newString);
        }
    }
}

Der obige code läuft wunderbar, aber wenn ich es installiert auf meinem Nexus s habe ich realisiert, dass es läuft ein bisschen zu langsam. Es dauert ein paar Sekunden. Etwa 3 oder 4 Sekunden, das ist inakzeptabel.
Jetzt habe ich gespielt einige Wort-Spiele auf meinem Handy und Sie berechnen alle Kombinationen einer string sofort das lässt mich glauben, dass mein Algorithmus ist nicht sehr effizient, und es kann verbessert werden. Kann mir jemand helfen?

public class TrieNode {
TrieNode a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
TrieNode[] children = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z};
private ArrayList<String> words = new ArrayList<String>();

public void addWord(String word){
    words.add(word);
}
public ArrayList<String> getWords(){
    return words;
}
}
public class Trie {

static String myWord;
static String myLetters = "afinnrty";
static char[] myChars;
static Sort sort;
static TrieNode myNode = new TrieNode();
static TrieNode currentNode;
static int y = 0;
static ArrayList<String> availableWords = new ArrayList<String>();

public static void main(String[] args) {

    readWords();
    getPermutations();
}
public static void getPermutations(){
    currentNode = myNode;
    for(int x = 0; x < myLetters.length(); x++){
        if(currentNode.children[myLetters.charAt(x) - 'a'] != null){
            //availableWords.addAll(currentNode.getWords());
            currentNode = currentNode.children[myLetters.charAt(x) - 'a'];
            System.out.println(currentNode.getWords() + "" + myLetters.charAt(x));
        }
    }
    //System.out.println(availableWords);
}
public static void readWords(){
    try {
        BufferedReader in = new BufferedReader(new FileReader("c://scrabbledictionary.txt"));
        String str;
        while ((str = in.readLine()) != null) {
            myWord = str;
            myChars = str.toCharArray();
            sort = new Sort(myChars);
            insert(myNode, myChars, 0);
        }
        in.close();
    } catch (IOException e) {
    }
}
public static void insert(TrieNode node, char[] myChars, int x){    
    if(x >= myChars.length){
        node.addWord(myWord);
        //System.out.println(node.getWords()+""+y);
        y++;
        return;
    }
    if(node.children[myChars[x]-'a'] == null){
        insert(node.children[myChars[x]-'a'] = new TrieNode(), myChars, x=x+1);
    }else{
        insert(node.children[myChars[x]-'a'], myChars, x=x+1);
    }
}
}
InformationsquelleAutor zataar | 2012-02-04
  1. 16

    In Ihrem aktuellen Ansatz, Sie suchen jede permutation der einzelnen Teilstrings. Also für "abc" Sie nachschlagen müssen "abc", "acb", "bac", "bca", "cab" und "cba". Wenn Sie wollte, zu finden, die alle Permutationen von "Permutationen", die Anzahl der Suchvorgänge ist fast 500,000,000, und das ist, bevor Sie haben sogar sah in seine Teilstrings. Aber wir können reduzieren diese zu eine lookup, unabhängig von der Länge, von der Vorverarbeitung Wörterbuch.

    Die Idee ist, jedes Wort in das Wörterbuch, in einigen Daten-Struktur, wobei jedes element enthält eine Reihe von Zeichen, und eine Liste aller Wörter, die (nur) diejenigen Zeichen. So zum Beispiel, könnten Sie bauen einen binären Baum, der hätte einen Knoten mit den (sortiert) Zeichensatz "abd" und das Wort Liste ["bad", "dab"]. Nun, wenn wir wollen finden, dass alle Permutationen von "dba", Sortieren wir es zu geben "abd" und schauen Sie sich in den Baum, um die Liste abzurufen.

    Als Baumann wies darauf hin, versucht sind gut geeignet zur Speicherung dieser Art von Daten. Die Schönheit des trie ist, dass die lookup-Zeit hängt nur von der Länge des Suchstrings - es ist unabhängig von der Größe Ihres Wörterbuchs. Da werden Sie speichern sehr viel von Worten, und die meisten von Ihre Suchbegriffe werden klein sein (die Mehrheit der 3-Zeichen-Teilfolgen von der niedrigsten Ebene Ihres Rekursion), diese Struktur ist ideal.

    In diesem Fall die Pfade auf Ihre versuche wider, die Zeichen setzt eher als die Worte selbst. Also, wenn Sie Ihre gesamte Wörterbuch war ["bad", "dab", "cab", "cable"], lookup-Struktur würde am Ende Aussehen wie diese:

    java-string-Permutationen und Kombinationen-lookup

    Es ist ein bisschen von einer Raum/Zeit-trade-off in der Weise, die Sie dies umsetzen. Im einfachsten (und schnellsten) Ansatz, jede Node enthält nur die Liste von Wörtern, und eine Reihe Node[26] von Kindern. Dies ermöglicht Ihnen, suchen Sie das Kind, bist du nach in konstanter Zeit, einfach durch einen Blick auf children[s.charAt(i)-'a'] (wo s ist dein Suchbegriff und i ist Ihre aktuelle Tiefe in der Marina).

    Der Nachteil ist, dass die meisten Ihrer children arrays sind meistens leer. Wenn der Raum ist ein Thema, können Sie eine kompaktere Darstellung, wie eine verknüpfte Liste, dynamischen Arrays, hash-Tabelle, etc. Jedoch, diese auf Kosten der potentiell erfordert mehrere Speicherzugriffe und Vergleiche bei jedem Knoten, statt der einfachen array-Zugriff von oben. Aber ich wäre überrascht, wenn der Platz verschwendet wurde mehr als ein paar Megabyte über das gesamte Wörterbuch, so dass die array-basierte Ansatz ist wahrscheinlich Ihre beste Wette.

    Mit der Marina im Ort, Ihre ganze permutation-Funktion ersetzt wird, die mit einer lookup, womit sich die Komplexität nach unten aus O(N! log D) (wo D ist die Größe des Wörterbuchs, N die Größe des Strings) zu O(N log N) (da müssen Sie zum Sortieren der Zeichen; die Suche selbst ist O(N)).

    EDIT: ich geworfen haben zusammen eine (ungetestete) Implementierung dieser Struktur: http://pastebin.com/Qfu93E80

    • Ich bekomme es zu 239500800 Permutationen (nicht 479001600). Haben Sie zählen die beiden ts als andere? Wenn das Wort war "aaa", dann denke ich, es wäre nur 1 permutation, nicht 6. Aber sonst eine gute Antwort, +1 von mir.
    • Ja, "aaa" hat nur eine bestimmte permutation, aber der Fragesteller den code nicht suchen, Duplikate, so ist es immer noch generieren 6 Kopien und tun, eine Suche für jeden.
    • Super!!!!!
    • gute Erklärung. +1
    • Es dauerte eine Weile, um zu verstehen, diese Daten-Struktur, aber ich endlich habe (glaube ich). Also ist der Knoten für diese Art von Baum würden, haben 26 Filialen. Eine für jedes Zeichen des Alphabets. Und würde jeder Knoten auch eine Liste, die enthält die entsprechenden Wörter für diesen Knoten. Ist das richtig?
    • Klingt ungefähr richtig. Ich habe ein paar Absätze über die details der Implementierung auf meine Antwort.
    • Also, wenn du den string "abcd" für das oben genannte Beispiel, wie würden Sie finden die Permutationen "cab", "schlecht" und "dab" da der Baum auf die Gabeln 'b'?
    • Diejenigen, die nicht die Permutationen von "abcd", Sie sind Permutationen von Zeichenketten "abcd". Diese Suche ersetzt Ihre permuteString() Funktion, aber Ihre subStrings() Funktion sonst bleiben die gleichen. Sie könnte build all diese Informationen in Ihre versuche (addiert man alle Worte für alle Teilfolgen in jedem Knoten), aber es wird viel länger dauern, um zu bauen, viel mehr Speicher, und wird sich nicht verbessern Ihre worst-case-performance. Aber wenn die version, die ich gegeben habe ist immer noch zu langsam, lassen Sie mich wissen und ich werde versuchen, näher auf diese alternative.
    • Ich habe den code Hinzugefügt, dass ich so weit zu der wichtigsten Frage. Bitte werfen Sie einen Blick auf es. Dank
    • Sieht alles richtig; ich sehe keine logischen Fehler. Aber ein paar Bereiche könnte ein bisschen Aufräumen, und es braucht eine gut definierte Schnittstelle, anstelle einer Reihe von statischen Variablen. Check this out: pastebin.com/Qfu93E80 (ungetestet, kann auch nicht kompilieren, geschweige denn arbeiten 😉 )
    • Vielen Dank für den polierten code. Testen werde ich es später.Das problem bei diesem code ist, dass, wenn Sie geben Sie ein Wort, dann wird es finden alle sub-Worten. Aber wenn Sie es einige Briefe an zufällig dann das system bricht zusammen und ich bin mir nicht sicher, was zu tun ist!
    • Ich verstehe nicht ganz Folgen. Wenn Sie es einige zufällige Buchstaben, es finden sollten Sie alle Permutationen von diesen zufälligen Buchstaben. Ist es das, was Sie erwarten? Wo und wie macht es "break down", genau?
    • Ich denke, ich bin immer noch nicht ganz klar darüber. Zum Beispiel, wenn Sie geben Sie das Wort "Infanterie" gibt es folgende [ ... ] eine [fa]f []i [fain, naif]n []n []r []t [Infanterie]y und wenn man es "abdefhilmp" es gibt []a []b [ab, ba]d [schlecht, dab]e [abed, bade, Perle]f []i []l schaut das OK für dich?
    • Sorry für die späte Antwort. Wenn Sie sagen: "es gibt die folgenden", ich bin nicht sicher, was genau "es" ist, oder wie Sie Sie verwenden. Wenn Sie könnten Ihre stick code auf pastebin.com ich nehme einen Blick.
    • Danke für die Antwort. Damals hatte ich verpasste den Teil, wo Sie sagte, ich muss noch mit den Teilstrings () - Funktion. Einmal habe ich die Versuche perfekt gearbeitet, aber ich lief in einige neue Probleme. Mein Nexus S Handy begann zu Force Close und mein Android-emulator gab eine (out-of-memory-Fehler) jemand sagte, dass diese Häufig auf Handys aufgrund des begrenzten Speichers. Eine Lösung ist das schreiben der Versuche Daten auf die SD-Karte. Ich bin mir nicht sicher, wie Sie Sie zu schreiben, wie eine Daten-Struktur auf eine SD-Karte. Haben Sie irgendwelche Hinweise?
    • Sie könnten versuchen, die weitere platzsparende version, die ich erwähnt - store ein Zeichen an jedem Knoten (wie in der Abbildung oben), und ersetzen Sie die TrieNode[26] mit einem ArrayList<TrieNode>. Tun Sie es direkt von der SD-Karte würde schwierig sein, und viel langsamer. By the way, wie viel Speicher verfügbar ist, um Ihre Anwendung? Wie groß ist dein Wörterbuch? Wie viele TrieNodes erstellt werden? Läuft es out of memory beim Bau der Marina, oder woanders?
    • Eigentlich die ArrayList ist, was ich verwendet habe. Mein Wörterbuch hat eine Größe von 53,818 Worte, die über 425KB. Ich habe gezählt 62,766 TrieNodes. Es läuft out of memory beim Bau der Marina und mein Handy kommt mit 512 MB RAM. Übrigens, ich habe es versucht mit über 40.000 Worte und es hat funktioniert!
    • Das klingt nicht richtig... ich würde erwarten, dass 62,766 Knoten auf deutlich unter 10 MB ist, selbst mit all den fast-leer 26-element-arrays. Ich glaube nicht, dass der Raum-effiziente Umsetzung sollte mehr als 2MB.
    • Mein Fehler! Es ist die Array-Implementierung anstelle der ArrayList. Wie viel mehr Speicher meinst du die Array-Implementierung erfordern würde? Ich habe auch gelesen auf dieser Website, Android-die Grenzen der Speicher pro app zu 24MB. Ich bin mir auch nicht sicher, wie wahr diese information ist!
    • Jedes array enthält 26 Zeigern, also 26*62766 insgesamt. Aber wir haben nur 62765 gültige Zeiger (eine für jeden Knoten, außer der Wurzel). Bei 4 Byte, dass ist ~200kB gültigen Zeiger und 6MB von null. So können Sie sparen ~6MB nur durch die Speicherung der gültigen Kinder. Der Nachteil ist, dass Sie verlieren, der konstant-Zeit-indizierte Suche in der child-array - Sie brauchen, um Suche durch die child-Liste an jedem Knoten für das nächste Zeichen.

    InformationsquelleAutor Nick Barnes
  2. 1

    Siehe hier: So finden Sie Liste der möglichen Wörter aus einer Buchstaben-matrix [Boggle Solver]

    Die Idee, die hinter dem code in die Antworten ist wie folgt:

    • Iteration über jedes Wort Wörterbuch.
    • Iterieren über die einzelnen Buchstaben im Wort, indem es auf eine Zeichenfolge und fügen Sie den string jedes mal, um ein array von Präfixen.
    • Beim anlegen von string-Kombinationen, test, um zu sehen, dass Sie existieren, in der Präfix-array vor Verzweigung zu fördern.
    InformationsquelleAutor mowwwalker
  3. 1
      static List<String> permutations(String a) {
    List<String> result=new LinkedList<String>();
    int len = a.length();
    if (len<=1){
      result.add(a);
    }else{
      for (int i=0;i<len; i++){
        for (String it:permutations(a.substring(0, i)+a.substring(i+1))){
          result.add(a.charAt(i)+it);
        }
      }
    }
    return result;
  }
    InformationsquelleAutor olaf
  4. 1

    Ich glaube nicht, dass das hinzufügen alle Permutationen notwendig ist. Sie können einfach Kapseln die Zeichenfolge in eine PermutationString:

    public class PermutationString {

    private final String innerString;

    public PermutationString(String innerString) {
        this.innerString = innerString;
    }

    @Override
    public int hashCode() {
        int hash = 0x00;
        String s1 = this.innerString;
        for(int i = 0; i < s1.length(); i++) {
            hash += s1.charAt(i);
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final PermutationString other = (PermutationString) obj;
        int nChars = 26;
        int[] chars = new int[nChars];
        String s1 = this.innerString;
        String s2 = other.innerString;
        if(s1.length() != s2.length()) {
            return false;
        }
        for(int i = 0; i < s1.length(); i++) {
            chars[s1.charAt(i)-'a']++;
        }
        for(int i = 0; i < s2.length(); i++) {
            chars[s2.charAt(i)-'a']--;
        }
        for(int i = 0; i < nChars; i++) {
            if(chars[i] != 0x00) {
                return false;
            }
        }
        return true;
    }

}

    Einen PermutationString ist ein string, aber wo zwei PermutationStrings sind gleich, wenn Sie die gleiche Frequenz von Zeichen. So new PermutationString("bad").equals(new PermutationString("dab")). Dies gilt auch für die .hashCode(): wenn die Streicher sind Permutationen voneinander, Sie erzeugen die gleiche .hashCode().

    Nun können Sie einfach eine HashMap<PermutationString,ArrayList<String>> wie folgt:

    HashMap<PermutationString,ArrayList<String>> hm = new HashMap<PermutationString,ArrayList<String>>();
String[] dictionary = new String[] {"foo","bar","oof"};
ArrayList<String> items;
for(String s : dictionary) {
    PermutationString ps = new PermutationString(s);
    if(hm.containsKey(ps)) {
        items = hm.get(ps);
        items.add(s);
    } else {
        items = new ArrayList<String>();
        items.add(s);
        hm.put(ps,items);
    }
}

    So, nun sind wir iterieren über alle möglichen Wörter im Wörterbuch, konstruieren Sie eine PermutationString als Schlüssel, und wenn die Schlüssel bereits vorhanden ist (das heißt, es gibt bereits ein Wort mit dem gleichen Zeichen Frequenzen), fügen wir einfach unser eigenes Wort zu ihm. Andernfalls fügen wir eine neue ArrayList<String> mit dem einzigen Wort.

    Nun haben wir gefüllt, bis das hm mit allen Permutationen (aber nicht so viel Schlüssel) können Sie Abfragen:

    hm.get(new PermutationString("ofo"));

    Diese zurück ArrayList<String> mit "foo" und "oof".

    Testcase:

    HashMap<PermutationString, ArrayList<String>> hm = new HashMap<PermutationString, ArrayList<String>>();
String[] dictionary = new String[]{"foo", "bar", "oof"};
ArrayList<String> items;
for (String s : dictionary) {
    PermutationString ps = new PermutationString(s);
    if (hm.containsKey(ps)) {
        items = hm.get(ps);
        items.add(s);
    } else {
        items = new ArrayList<String>();
        items.add(s);
        hm.put(ps, items);
    }
}
Assert.assertNull(hm.get(new PermutationString("baa")));
Assert.assertNull(hm.get(new PermutationString("brr")));
Assert.assertNotNull(hm.get(new PermutationString("bar")));
Assert.assertEquals(1,hm.get(new PermutationString("bar")).size());
Assert.assertNotNull(hm.get(new PermutationString("rab")));
Assert.assertEquals(1,hm.get(new PermutationString("rab")).size());
Assert.assertNotNull(hm.get(new PermutationString("foo")));
Assert.assertEquals(2,hm.get(new PermutationString("foo")).size());
Assert.assertNotNull(hm.get(new PermutationString("ofo")));
Assert.assertEquals(2,hm.get(new PermutationString("ofo")).size());
Assert.assertNotNull(hm.get(new PermutationString("oof")));
Assert.assertEquals(2,hm.get(new PermutationString("oof")).size());
    InformationsquelleAutor Willem Van Onsem
  5. 0

    Verwenden Trie

    Anstelle der Prüfung alle N! Möglichkeiten, Sie Folgen nur Präfix-Bäumen, führen zu einem Ergebnis. Dies wird significanlty reduzieren die Menge der Zeichenfolgen, die Sie überprüft haben, gegen.

    InformationsquelleAutor The Real Baumann
  6. 0

    Gut, Sie erweitern Ihr Wörterbuch Entitäten mit array letters[] wo letters[i] bleibt für Zeiten, die i-te Buchstabe des Alphabets in diesem Wort. Es werden einige zusätzliche Speicher nicht weit, als es die jetzt verwendet wird.

    Dann für jedes Wort die Permutationen, die Sie überprüfen möchten, werden Sie brauchen, um count-Anzahl der unterschiedlichen Buchstaben zu und dann traverse durch dictiory mit einfachem Vergleich Verfahren. Wenn für alle Buchstaben für Wort aus dem Wörterbuch Zahl der Ereignisse weniger oder gleich für Wort prüfen wir - ja, dieses Wort dargestellt werden kann als permutation von substring, sonst - Nein.

    Komplexität: es nahm O(D * maxLen) für die Vorberechnung und O(max(N, D)) für jede Abfrage.

    • Die Abfrage muss nicht sein, O(D). Sie sind auf der Suche nach einem bestimmten letters[] array; wenn Sie Art Ihrem Wörterbuch nach, um diese arrays können Sie finden, die Sie suchen, in O(logD). Das ist ziemlich viel, was meine Lösung oben tut.
    InformationsquelleAutor OleGG
Schreibe einen Kommentar