Buchstabensalat entschlüsseln
-
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.
-
Eine Möglichkeit ist es auch, auf die "Kombinationswahrscheinlichkeiten" der Buchstaben in der betreffenden Sprache zuzugreifen, wenn man diese verfügbar hat. In jeder normalen Sprache kommen verschiedene Kompinationen (z.b. ie in Deutsch) viel häufiger vor als andere wie z.B xx. Dann probiert man zuerst die wahrscheinlicheren Permutationen der Suchmenge aus, um die astronomische Zahl an Möglichkeiten einzuschränken. Dies wird um so effizienter, um so lägere Zeichenketten man für die Wahrscheinlichkeiten heranzieht, also betrachtet man dafür nut das letzte Zeichen im bisherigen String, so ist es noch recht ungenau aber bei zwei oder drei Zeichen wird es extrem effizient, solange vor allem lesbare Wörter der betreffenden Sprache vorkommen.
Diese gefundenen Möglichkeiten vergleicht man dann mit einem Wörterbuch und sucht solange immer unwahrscheinlichere Kombinationen durch, bis man eine gültige gefunden hat oder alle Kombinationen abgesucht sind.Also, man nimmt als erstes den am Wortanfang am häufigsten vorkommenden Buchstaben, fügt dann den am häufigsten dahinter stehenden Buchstaben aus der Suchmenge ein und so weiter. Diesen enthaltenen String prüft man, ist er keine Lösung, so nimmt man den nächstwahrscheinlichen.
Leider sind die benötigten Wahrscheinlichkeuitstabellen schwer zu beschaffen...