Wirklich große Permutationsliste

Meine Frage ist nicht sprachspezifisch. Ich habe Probleme damit, die Schleife zur Verarbeitung von Permutationen zu bekommen. Ich versuche, etwas zu codieren, um alle Werte für 26^x anzuzeigen, wobei x die Länge einer Zeichenfolge ist. Kein Eingabestring wird geliefert werden, so wenn x=1, wird es ein durch z, wenn x=2 itll Anzeige aa durch zz anzuzeigen. az wird als verschieden von za gesehen.Wirklich große Permutationsliste

Genauer gesagt, ich möchte dies für längere Strings, mehr als 100 Zeichen in der Länge zu versuchen, um zu sehen, wie viele Strings einer gegebenen Länge Wörter im Gegensatz zu zufälligen Buchstaben enthalten.

Quelle

2012-04-13 Rickie Marsh

Zeit Komplexität und Anzahl der Wörter ist n !, für 100 Zeichen ist 9 * 10^157. Jeder Algorithmus braucht eine LANGE Zeit, um die Wörter viel weniger zu verarbeiten. –

(Von was ich verstehe) Sie können die Anzahl der Wörter für eine Länge berechnen, die Ihr Programm produzieren würde. Verwenden Sie eine Wörterbuchbibliothek, um die Anzahl der Wörter mit der angegebenen Länge zu zählen. Jetzt können Sie die Anzahl der Wörter mit zufälligem Buchstaben sehen. –

@JesusRamos Sie können eine faire Münze 1000001 Mal werfen und simulieren, es dauert 2^1000001 Schritte, aber es dauert fast keine Zeit vorherzusagen, ob 'Heads' gewonnen oder verloren haben! – ElKamina

Pro Kommentar zu der Frage ist es etwas unpraktisch zu versuchen, alle möglichen 100-Zeichen-Strings aufzuzählen.

Ich würde vorschlagen, die alternative Strategie der Generierung zufälliger Strings der gegebenen Länge, anstatt in einer strukturierten Art und Weise aufzuzählen. Etwas wie:

count = 0 
for i from 0 to simulation_length: 
    random_string = '' 
    for j from 0 to string_length: 
     random_string += random_char() 
    // containsWord(string) checks if the random string contains a word 
    // this is tricky in and of itself 
    if (containsWord(random_string)) count++ 
...

Die Stichprobe wird Ihnen eine Darstellung des Verhaltens über den gesamten Raum, solange simulation_length ausreichend ist.

Quelle

2012-04-13 05:15:53 mfrankli

Sie könnten dies viel direkter tun, indem Sie die Gesamtzahl der Wörter für jede Länge 'n' und dividieren durch' n! ', was der Teil der Buchstabenketten der Länge' n' ist, die Wörter sind. Ich denke, dass das OP darum bittet, Wörter als Teilmenge zu enthalten, was jedoch schwieriger ist. – Dougal

Ja, das war meine Interpretation auch (daher meine Antwort, die sonst nicht viel Sinn macht), aber der Code spiegelt es nicht wirklich richtig wider. bearbeitet werden ... – mfrankli

26^x, wobei x die Länge einer Zeichenkette ... Ich bin zu wollen dies für längere Strings laufen, mehr als 100 Zeichen lang

Sie es vergessen sollten.

Lassen Sie uns die Dinge in die richtige Perspektive bringen. Es gibt 26 Buchstaben in Englisch Alphabet, so Gesamtzahl der Saiten mit 100 Zeichen in ihnen ist ...

3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376

Das Dezimalzahl ist. Bei einer Geschwindigkeit von 1 String pro Millisekunde dauert es 9,9 * 10^130 Jahre, um alle zu drucken. Das ist 7.3 * 10^120 mal länger als das Universum existiert hat.

Eine Wörterliste oder ein Wörterbuch in den Speicher laden und stattdessen verwenden.

Quelle

2012-04-13 05:17:51 SigTerm

Ich habe verstanden, dass viel in das geht. Ich plane, eine zufällige manuelle Überprüfung mit den ersten zwei Zeichen durchzuführen. Wenn es nicht möglich ist, ein Wort zu beginnen, gibt es diesen Pfad auf. Ich habe wahrscheinlich meine Frage falsch formuliert, da sie mehr bei zwei Zeichen beginnt, prüft, ob ein Wort möglich ist, wenn ja, ein weiteres Zeichen hinzufügen und wiederholen, bis entweder die Wörter nicht mehr möglich sind oder die Zeichenfolgenlänge erreicht ist. Wenn nicht möglich, gehen Sie zum nächsten Buchstaben an dieser Position. –

Eine ordentliche Such-/Verarbeitungsmenge kann durch Festlegen einiger einfacher Regeln für die ersten beiden Zeichen eliminiert werden. Wenn q der erste ist, kann der zweite nur ein Vokal sein. Das Gleiche gilt meistens für einige andere Buchstaben. 26^2 mögliche Zwei-Buchstaben-Kombinationen, q zum Beispiel hat nur 5 gültige Kombinationen, wo es der erste Buchstabe ist. Es wird zwar immer noch nicht Spaß machen, so viele Regeln zu setzen, aber das Problem wird dadurch etwas gelöst. Da ich auch Strings mit einem bestimmten Wort an einem bestimmten Ort betrachte, kann es in zwei Abschnitten vor und nach dem Wort aufgeteilt werden. –

Was wir jetzt sehen möchten, ist: Wie viele Strings der Größe 50, 51, 52, ... können aus einem Wörterbuch mit folgenden Wortlen aufgebaut werden: "2: 183, 3: 815, 4: 3181, 5: 6151, 6: 9317, 7: 11962, 8: 11979, 9: 10400, 10: 8065, ... "? Nimm deine Werte von 'für n in {2..20}; do echo -ne "$ n \ t"; egrep -v ". * 's"/usr/teilen/dict/american-english | egrep -c "^. {" $ n "} $"; done' –

Es hängt von Ihrer Definition von "Wort" ab. Wenn 'a' ein Wort ist, ist es sehr einfach, eine untere Grenze für die Wahrscheinlichkeit zu erhalten, ein Wort in einer 100-Zeichen-Sequenz zu erhalten (ungefähr 1 - 1/e^4). Ähnlich können Sie zwei Buchstaben Wörter und drei Buchstaben Wörter betrachten und die Wahrscheinlichkeit verfeinern. Nach 4 oder 5 Buchstaben wird diese Wahrscheinlichkeit sehr genau, da es wenige längere Wörter gibt und diese zufällig auftreten.

Quelle

2012-04-13 06:42:25 ElKamina

Es ist mehr als ein Wort in der angegebenen Zeichenfolge Länge geben. Wenn der Benutzer 8 eingibt, könnte er "itisadog" oder "wesaidno" zurückgeben. Wenn man es so anschaut, scheint es ein besseres Wörterbuch zu geben und nach allen Wörtern zu suchen, die zu der gegebenen Länge addiert werden können. –

@RickieMarsh: Aber du erwartest nicht, dass sie Sinn ergeben? Also wären 'nosaidwe' und' nonoweno' auch passend? –

Wirklich große Permutationsliste

Antwort

Verwandte Themen