Anzahl verschiedener Kombinationen

[Die Muhkuh]

Hi,

ich stehe gerade vor einem mathematischem Problem, bei dem ich hoffe, dass mir jemand weiterhelfen kann.

Angenommen ich hab einen String, der immer 10 Zeichen lang ist. Wie viele verschiedene, eindeutige Kombinationen kann man bilden, wenn man folgendes beachtet:

• Es dürfen nur die 26 Buchstaben aus dem Alphabet und die Zahlen 0 - 9 vorkommen
• Groß- und Kleinschreibung wird beachtet (abc ist nicht gleich Abc usw.)
• Buchstaben und Zahlen dürfen auch mehrfach bzw. gar nicht auftreten

Hat jemand eine Idee, wie man das ausrechnen kann?

[jfheins]

(mögliche Kombinationen für eine Stelle)^(Stellen)

Also bei Groß- und Kleinbuchstaben + Zahlen sind das 26+26+10 = 62 Möglichkeiten für eine Stelle.

62^10 = 839299365868340224 Möglichkeiten ;)

[Die Muhkuh]

Uhi :shock: Das ging ja schnell. :stupid:

Danke :)

[himitsu]

26 Große + 26 Kleine + 10 Zahlen = 62


1 Buchstabe lang = 62 Möglichkeiten
2 Buchstaben lang ist 62*62 Möglichkeiten
3 Buchstaben lang ist 62*62*62 Möglichkeiten
...
10 Buchstaben lang = 62^10 Möglichkeiten = 839.299.365.868.340.224

[add]
da zickt mal 'nen Sekündchen das Inet und schon ist wer schneller :cry:

[BAMatze]

also das mit den Potenzen müsste ich nochmal überdenken, aber ich bin der Meinung das für die Kombinatorik (was das Problem ja darstellt) eigentlich die Fakultät genutzt wird.

Bitte erschlagt mich nicht, wenn ich falsch liege, ich grüble selber gerade. hier mal schnell in Wiki geschaut.

MfG
BAMatze

[DeddyH]

Die Potenzrechnung ist schon korrekt, das Dualsystem basiert ja z.B. auch darauf.

[gammatester]

62^10 ist falsch, da offensichtlich Zahlen im Gegensatz zu Buchstaben nicht doppelt auftreten dürfen.

[BAMatze]

Kombinatorik

Ich kenne das nur so, von der Berechnung der Variationen im Lotto (ein ähnliches Problem), allerdings unterscheidet es sich ja schon von dem hier gestellten Problem, weil jede Zahl im Lotto nur 1 Mal vorkommen darf. Deswegen grübel ich auch gerade, ob Potenzen nicht doch richtig sein könnten, wenn Buchstaben/ Zahlen mehrfach vorkommen können.

[gammatester]

Zu mindest scheint es kein einfaches kombinatorische Grundproblem zu sein. Ein Ansatz:

Gesamtzahl = (Anzahl mit 0 Zahlen) + (Anzahl mit 1 Zahl) + (Anzahl mit 2 Zahlen) + ..+ (Anzahl mit 10 Zahlen)
= 52^10 + 52^9*10*10 + .. 10!

[BAMatze]

Revidiere das mit der Fakultät, damit kann nicht die gewünschte Funktionalität (also das mehrfache Vorkommen eines Buchstabens) erreicht werden. Wie vorher schon gesagt wurde (hab es im Dualsystem mir gerade angeschaut) gilt auch 4Stellen a 2 verschiedenen Zeichen ergibt 16 und das erreicht man nur mit Potenzen.

Gegenbeweis (also das Fakultät auch funktionieren würde) wäre, wenn 2! oder 4! 16 ergeben würde, allerdings ist 2! = 2 und 4! = 24. Somit kann die Fakultät nicht stimmen! (Das letzte ist kein Fakultätszeichen :mrgreen: )

Sorry für den falschen Einwurf. Hab gleich an Kombinatorik gedacht.

MfG BAMatze

[gammatester]

Zitat:

Zitat von BAMatze

Revidiere das mit der Fakultät, damit kann nicht die gewünschte Funktionalität (also das mehrfache Vorkommen eines Buchstabens) erreicht werden.

Bezieht sich das auf meinen Ansatz? Dann hast Du etwas falsch verstanden: Die 10! ist er letzte Summand, nämlich der für 10 Zahlen. Und die 10 verschiedenen(!) Ziffern lassen sich nun mal auf genau 10! Möglichkeiten anordnen.

[Die Muhkuh]

Ohje ohje, sorry, das war nur ein Fehler von mir :oops:

Die gültigen Zeichen dürfen mehrfach auftreten, also Zahlen und Buchstaben :)

[gammatester]

Zitat:

Zitat von Die Muhkuh

Ohje ohje, sorry, das war nur ein Fehler von mir :oops:

Die gültigen Zeichen dürfen mehrfach auftreten, also Zahlen und Buchstaben :)

Dann schließe ich mich der Zahl 62^10 von jfheins aus Beitrag #2 an.

[himitsu]

ansonsten kann man es auch manuell ausprobieren, auch wenn es mit 26x10 etwas schwer wird

Code:

3x1  3x2  3x3
=    =    =
3^1  3^2  3^3
=    =    =
3    9    27


1    11   111
2    21   211
3    31   311
     12   121
     22   221
     32   321
     13   131
     23   231
     33   331
          112
          212
          312
          122
          222
          322
          132
          232
          332
          113
          213
          313
          123
          223
          323
          133
          233
          333

[Die Muhkuh]

Zitat:

auch wenn es mit 26x10 etwas schwer wird

26x26x10 um genau zu sein ;)

[Hansa]

Wer hat das mit dem Lotto gesagt ? Es geht um Wahrscheinlichkeitsrechnung. Es gibt zwei Möglichkeiten : Gezogene Kugel zurücklegen oder eben nicht ! Erste Möglichkeit ist die Potenz, die zweite : Fakultät n!.

[BoolString]

Nur mal als Einwurf von der Seite:

Delphi-Quellcode:

Procedure TForm1.CalcCombinatoricGenes (CombinatoricResult, Rest : String; CalcDepth : Integer);
Var Runner  : Longint;
    Counter : Int64;
Begin
  If (Rest='') Or (CalcDepth=0) THen
  Begin
   ListBox1.Items.Add (CombinatoricResult);
  end
  Else
  Begin
    For Runner := 1 to Length (Rest) do
    Begin
      CalcCombinatoricGenes (CombinatoricResult + Rest [Runner],
                               Copy (Rest, 1, Runner-1) + Copy (Rest, Runner+1, Length (Rest)-1),
                               CalcDepth-1);
    end;
  end;
end;



procedure TForm1.BitBtn1Click(Sender: TObject);
begin
  CalcCombinatoricGenes ( '', '123456789', 5);
end;

Der Source (ungetestet und aus einem alten Projekt rauskopiert) liefert alle Kombinationen aus den Chars '1'..'9' der Länge 5.

Liebe Grüße aus ><)))°> Town

Jan

[BAMatze]

Zitat:

Zitat von Hansa

Wer hat das mit dem Lotto gesagt ? Es geht um Wahrscheinlichkeitsrechnung. Es gibt zwei Möglichkeiten : Gezogene Kugel zurücklegen oder eben nicht ! Erste Möglichkeit ist die Potenz, die zweite : Fakultät n!.

Naja bei Fakultäten geht es eigentlich erstmal um Variationsmöglichkeiten.

Zitat:

In der abzählenden Kombinatorik spielen Fakultäten eine wichtige Rolle, weil n! die Anzahl der Möglichkeiten ist, n unterscheidbare Gegenstände in einer Reihe anzuordnen.

erst mit der Möglichkeit die Gesamtanzahl aller Möglichkeiten zu berechnen, ist man in der Lage die Wahrscheinlichkeit 1 Kombination zu bestimmen, was ja logischer Weise 1/Gesamtzahl (*100, wenn man es in Prozent haben möchte) ist.

Und diesen Einwurf der Fakultät habe ich ja auch schon wiederrufen.

[Codewalker]

Mal eine kleine Übersicht als Auszug aus einer Kombinatorik-Vorlesung

Geordnet bedeutet hier, dass die Reihenfolge wichtig ist. Wenn es geordnet sein muss ist z.B. 123 ein anderes Ergebnis als 321, andernfalls nicht.
Zurücklegen bedeutet, ob ein Element doppelt vorkommen kann (man es also symbolisch gesehen, nach dem Ziehen wieder in die Lostrommel zurücklegt oder nicht)

Im Folgenden nennen wir die Menge unserer möglichen Elemente A und die Anzahl aller Elemente in A nennen wir n. Wir ziehen jeweils k viele Objekte.

k-Tupel
geordnet: ja
zurücklegen: ja

Mathematisch: k-Tupel über A
Bezeichnung: k-Tupel
Formel für die Anzahl: n^k

Beispiele: Passwörter der Länge k bei n verschiedenen Zeichen (z.B. wie oben 62).

k-Permutation
geordnet: ja
zurücklegen: nein

Mathematisch: k-Tupel über A ohne Wiederholungen
Bezeichnung: k-Permutation
Formel für die Anzahl: n! / (n-k)!

Beispiele: Bundesligatabelle ( k = n = 18 )
Medaillengewinner im 100m Finale (die drei verschiedenen Medaillen sind ja unterschiedlich wertvoll, daher ist die Reihenfolge wichtig) (n = 8, k = 3)

k-Kombination
geordnet: nein
zurücklegen: nein

Mathematisch: k-elementige Teilmengen von A
Bezeichnung: k-Kombination
Formel für die Anzahl: n! / k!(n-k)!

Beispiele: Lottoschein (n = 49, k = 6)
Bundesligaabsteiger (n = 18, k = 3)
Starthand beim Skat (n = 32, k = 10)

k-Multimenge
geordnet: nein
zurücklegen: ja

Mathematisch: "ungeordnete" k-Tupel über A
Bezeichnung: k-Multimenge
Formel für die Anzahl: (n+k-1) / k!(n-1)!

Beispiele: Kniffel (n = 6, k = 5)
Notenspiegel bei k Klausurteilnehmern (n = 11 für die Noten 1.0 bis 5.0)




Je nach Aufgabenstellung kann man das ganze dann entsprechend kombinieren. Bei Bedarf kann ich auch noch ein paar Aufgaben mit Lösungen dazu ausgraben.