Buchstabensalat entschlüsseln
-
Hallo,
ich habe eine Buchstabenfolge von 25 Buchstaben, diese sind wahllos durcheinander
gemischt. In der richtigen Reihenfolge sollen sie einen deutschen Satz ergeben.
Leer-/Satzzeichen gibt es keine und Umlaute "äüöß" ebenfalls nicht.
Wie kann ich nun unter C++ ein Programm entwickeln der mir sämtliche Kombinationen
von Buchstaben ermittelt und ich somit den Text entschlüsseln kann. Später kommen
noch Kriterien dazu wie z.B. Buchstabenkombinationen wie "xy" können nicht vorkommen
usw.
Ich bin für jeden Tipp dankbar.
-
Nehmen wir an, dass 52 Nutzzeichen (2 x 26) im Zeichensatz vorkommen koennen, dann sind das immer noch 52 hoch 25 Kombinationsmoeglichkeiten.
Um die Anzahl der Kombinationen zu begrenzen, muesstest Du auf ein elektronisches Woerterbuch zugreifen. (siehe z.B. GNU ispell library)
-
Hallo,
Vielleicht nützt dir die STL-Funktion next_permutation aus algorithm etwas.
-
kommt mir irgendwie bekannt vor
-
@Power Off
Soviel ich die Frage verstanden habe, will er von einer Zeichenkette mit 25 Buchstaben alle Variationen haben, nicht alle Möglichkeiten aller Buchstaben in einem 25er String. Das ist also nicht 52hoch25 sondern lediglich 325.
-
das ist so nicht richtig:
abc...xyz
^
25*26 buchstaben, macht '25 zeichen * 26 buchstaben = 650'
-
also verklagt mich, aber um aus 25 gegebenen Zeichen ein Wort der Länge 25 herzustellen, sollte es doch 25! Möglichkeiten geben:
25 moegliche Zeichen stehen als erster Buchstabe zur Auswahl, 24 fuer den zweiten, 23 fuer den dritten usw....
-
@enno-tyrant
Hää?
Wieso denn 25*26. Du hast 25 Zeichen die verschieden angeordnet werden können.
Das mit den 325 ist ja auch falsch. Die Höchstanzahl wäre 25!. Das sind 15511210043330985984000000 Möglichkeiten. Allerdings wiederholen sich sicher einige Buchstaben so dass es weniger wird.
-
nein, blue-tiger hat recht:
es sind 25*26-26 zeichen, für jedes zeichen stehen 26 buchstaben zur verfügung -> bei jedem weiteren zeichen verringert sich die anzahl der buchstaben aus dem pool um eins.
wie blue-tiger es schon schrieb: [Z=zeichen; BS=buchstabe]
1.Z (26 BS), 2.Z (25 BS), 3.Z (24 BS) etc.ppsomit ergibt das: 25 Z * 26 BS - 26 BS = 625 möglichkeiten (ist ein zeichen doppelt gehts noch schneller)
-
Lies dir Blue-Tigers Post noch mal durch.
-
nagut, ich meinte auch nicht das er in jedem sinne recht hat, er brachte aber aber auf diese rechnung die ich 'veröffentlichte'
-
Nö
-
enno-tyrant schrieb:
nagut, ich meinte auch nicht das er in jedem sinne recht hat, er brachte aber aber auf diese rechnung die ich 'veröffentlichte'
ehm.... wirklich nö, wie du selber sagst:
enno-tyrant schrieb:
nein, blue-tiger hat recht:
es sind 25*26-26 zeichen, für jedes zeichen stehen 26 buchstaben zur verfügung -> bei jedem weiteren zeichen verringert sich die anzahl der buchstaben aus dem pool um eins.
wie blue-tiger es schon schrieb: [Z=zeichen; BS=buchstabe]
1.Z (26 BS), 2.Z (25 BS), 3.Z (24 BS) etc.pp
...1. Zeichen: 25 moegliche Buchstaben stehen zur Auswahl.
fuer jede dieser 25 Moeglichkeiten gibts jetzt wieder 24 verschiedene Auswahlmoeglichkeiten fuer das zweite Zeichen. Ergibt 25 * 24 verschiedene Moeglichkeiten fuer die ersten beiden Buchstaben.Dann haben wir 2 Buchstaben "verbraucht", sind also immer noch 23 uebrig. und fuer jede der 25 * 24 Moeglichkeiten gibts wieder 23 verschiedene Moeglichkeiten, ein 3tes Zeichen auszuwaehlen. also 25 * 24 * 23 verschiedene Moeglichkeiten fuer 3buchstabige Woerter.
Aber wir wollen ja alle 25 Buchstaben aufbrauchen, d.h. am Ende haben wir
25 * 24 * 23 * 22 * ... * 4 * 3 * 2 * 1 = 25! verschiedene Moeglichkeiten, wie Braunstein auch schon gesagt hat.
Wenn diese Erklaerung bei dir nicht greift, dann sie's demokratisch: 2 gegen 1, du bist ueberstimmt :p
-
jetzt bin ich völlig durcheinander...was solls, die demokratie hat entschieden
-
Ich wusste gar nicht, dass wir hier eine Demokratie haben. Ich dachte immer, Marcus ist der König, die Moderatoren die Fürsten und wir das arme Fussvolk.
Ok, wird jetzt langsam zu OT.Cio
-
Ich würd sagen du hast 25 Buchstaben, wovon jeder an 25 verschiedenen Stellen stehen kann also :
25 * 25 = 625 oder ?
-
Damit wir das ein für allemal klären, hilfte vielleicht dieser Link
http://www.faes.de/Basis/Basis-Mathematik/Mathematik_Kombinatorik_Permut/mathematik_kombinatorik_permut.html
oder dieser (etwas ausführlicher)
http://www.phil.uni-sb.de/~jakobs/seminar/tutorium/kombinatorik/permutation.htm
-
wollte gerade das gleiche beweisen mit dem hier:
asdf asfd adsf adfs afsd afds sadf safd sdfa sdaf sfad sfda dfsa dfas dafs dasf dsfa dsaf fasd fads fsda fsad fdsa fdasaber du warst schneller..
btw, das ganze ist verwandt mit meiner frage hier: http://www.c-plusplus.net/forum/viewtopic.php?t=102276
nur ist das dort noch komplizierter, weil elemente ausgelassen werden können..
-konfusius
-
Die Frage habt ihr noch immer nicht beantwortet, denn ihr habt lediglich erst gelöst wieviele Möglichkeiten es gibt.
Mein Vorschlag wäre es mit Schleifen zu versuchen, der Code wird dadurch ein wenig unleserlich aber es müsste funktionieren.
Den Code kann ich dir zur Zeit nicht geben.
Mfg. MZ04.
-
schön und gut, aber _womit_ sollen die ausgaben verglichen werden? kann doch nicht sinn und zweck sein alle ausgaben zu lesen bis man den richtigen satz hat.
-
MZ04 schrieb:
Die Frage habt ihr noch immer nicht beantwortet [...]
Mfg. MZ04.Bereits im dritten Post in diesem Thread wird std::next_permutation erwaehnt
Man muss dann "nur" noch fuer jedes moegliche Ergebnis nachpruefen, ob es denn ein gueltiges Wort ist oder nicht... eben indem man es z. B. mit einer Wortliste vergleicht. Ist zwar aufwaendig, aber machbar.