Denkproblem

02/09/2012 22:08 vwap#1
Hey, ich schreibe derzeit einen kleinen Algorithmus, um eine Wort-Liste zu erstellen.
Dieser funktioniert auch wunderbar, ich möchte jedoch schon im Vorraus berechnen, wieviele Wörter man am Ende erhält, und so schon die vorraussichtliche Größe des Dokuments berrechnen.

Folgende Angaben sind dazu relevant:
  • Länge des Worts
  • Welche Buchstaben zur Erstellung verwendet werden dürfen
Derzeit wird eine Wortlänge von "6" verwendet.
Das Wort sieht am Ende also so aus:
"xxxxxx".

Folgende Zeichen dürfen verwendet werden:
  • A-Z
  • a-z
  • 0-9
  • . , ! ? - _ =
Mit diesen Angaben werden Wörter im folgenden Format erstellt:


Code:
AAAAAA
AAAAAB
AAAAAC
..
AAAABA
AAAABB
AAAABC
AAAABD
..
Und so weiter, bis alle Buchstabenkombinationen erstellt wurden.
Dies funktioniert, wie bereits gesagt, ohne Probleme.


Wie berechne ich nun schon vor dem Erstellen, wieviele Wörter erstellt werden?
02/09/2012 22:14 Che#2
möglichkeiten^wortlänge

A-Z = 26 zeichen
a-z = 26 zeichen
0-9 = 10 zeichen
. , ! ? - _ = = 7 zeichen
__
69 mögliche zeichen

bei der festen länge von 6 zeichen wäre das also 69^6 = 69*69*69*69*69*69* = 107918163081 möglichkeiten


wenn du alle wörter mit einer maximalen länge von 6 zeichen berechnen willst, dann musst du alle davor auch noch mit einberechnen, also:
69^1 + 69^2 + 69^3 + 69^4 + 69^5 + 69^6 = 107918163081 + 1564031349 + 22667121 + 328509 + 4761 + 69 = 109505194890 möglichkeiten
02/09/2012 22:14 Lobatto#3
War das nicht so : (Anzahl der möglichen Zeichen) ^ (Zahl der Stellen der Kombinationen)
Bei dir also dann 69^6 = 107'918'163'081
Bin mir aber gerade auch nicht ganz sicher

LG
02/09/2012 22:18 Mashkin#4
#2 und #3 haben Recht... solange alle Zeichen beliebig oft vorkommen dürfen und deine Wörter nicht höchstens sondern genau sechs Zeichen haben sollen.
02/09/2012 22:25 Che#5
Quote:
Originally Posted by M@shkin View Post
#2 und #3 haben Recht... solange alle Zeichen beliebig oft vorkommen dürfen und deine Wörter nicht höchstens sondern genau sechs Zeichen haben sollen.
hab auch gepostet wie es mit allen wortlängen bis zu ner bestimmten länge geht, also von daher habe ich komplett recht und nicht nur in einem bestimmten fall ;O
02/09/2012 22:30 _revo#6
Ich verleihe Che hiermit hochoffiziell einen goldenen Schulterklopfer für die Lösung dieses wirklich anspruchsvollen mathematischen Problems!
02/09/2012 22:30 vwap#7
Ja danke - funktioniert.
02/10/2012 00:05 Mashkin#8
Quote:
Originally Posted by 〤Che〤 View Post
hab auch gepostet wie es mit allen wortlängen bis zu ner bestimmten länge geht, also von daher habe ich komplett recht und nicht nur in einem bestimmten fall ;O
Mit den aufgeführten Ausnahmen meine ich eher, dass eure Lösungen nur bei einer festen Wortlänge und Zeichenwiederholung gilt.
Außerdem ist vorausgesetzt, dass die Zeichenreihenfolge von Bedeutung ist.

In diesem Fall sind alle drei Kriterien erfüllt, aber der Term wäre ungültig für beispielsweise folgende Situation:
-Die Zeichenreihenfolge ist egal (nur von Bedeutung ist, welche Zeichen enthalten sind)
-Zeichen dürfen/sollen sich nicht wiederholen (wie oben)
-Die Anzahl enhaltener Zeichen ist auf bis zu einem/zwei Grenzwert(en) limitiert, aber ansonsten variabel
02/10/2012 00:20 Horsedick.MPEG​#9
#closed