Buchstabensalat entschlüsseln

[Braunstein]

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

[Tom555]

Ich würd sagen du hast 25 Buchstaben, wovon jeder an 25 verschiedenen Stellen stehen kann also :

25 * 25 = 625 oder ?

[Braunstein]

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

[konfusius]

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
fdas

aber 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

[MZ04]

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.

[enno-tyrant]

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.

[Blue-Tiger]

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.

[sirniko]

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...

[Braunstein]

Hallo,

Man könnte auch Listen der am häufigsten verwendeten Wörter heranziehen und daran festmachen ob man etwas Verständliches gefunden hat. Sätze in denen mehrere derartige Wörter vorkommen, könnten gespeichert und seperat begutachtet werden. Wortlisten gibts z.Bsp. hier http://wortschatz.uni-leipzig.de/ (unter Punkt Wortlisten). Es wird trotzdem sehr aufwendig.
Wichtig wäre noch zu wissen, ob ein sinnvoller Satz möglich ist. Wenn z.Bsp. 24 gleiche Buchstaben vorkommen braucht man garnicht erst zu suchen.
Wenn man genauer drüber nachdenkt fallen Einem bestimmt noch mehr Kriterien ein.

Ciao

[lookias]

Fuer Algorithmen und Programmierung Hausarbeit sollte es reichen

alle Kombinationen zu speichern (natuerlich in lsiten von strings)

diese dann nach unmoeglichen Dingen wie xy zu durchsuchen

diese dann zu Streichen und die uebrigbleibenden welche wenig sein sollten

auszugeben

Dazu ist aber ein gewisses Grundwissen von c++ von noeten

[Braunstein]

Ich würds eher gleich prüfen und nur für gut befundene Varianten speichern. Bei 25 Buchstaben ist die Anzahl aller Varianten so gross, dass du das niemals in den Speicher oder auf die Fesplatte bekommst.