Wo sind die Mathe- und Informatikfüchse?

Computer: Software & Programmierung Visual Basic
#1

Ich habe hier eine Problemstellung und - Schande über mich - den totalen Black-out…

Problem: Gegeben sind X Zeichen (beispielsweise für x=11 die 11 Buchstaben von „A“ bis „K“ oder die Zahlen von 1 bis 11).

Aus diesen 11 Zeichen sollen nun Paare gebildet werden. Ok, nichts einfacher als das - aus 11 Zeichen lassen sich 55 Paare bilden. Diese Lösung lässt sich an Hand der entsprechenden Formel aus der Kombinatorik ermitteln.

Jetzt stellen wir uns diese 55 Paare untereinandergeschrieben vor…

Wenn wir nunmehr immer 4 Zeichen in eine Zeile schreiben, so sind darin ja immer gleichzeitig 6 Paare vertreten. Zum Beispiel ABCD = „AB“, „AC“, „AD“, „BC“, „BD“ und „CD“.

  1. Aufgabe: Wie ermittelt man rein rechnerisch die Anzahl der Zeilen (oder anders ausgedrückt die Anzahl der 4er-Kombinationen), die mindestens erforderlich sind, um alle Zeichenpaare abzubilden (einfach 55 \ 6 +1??)

  2. Aufgabe: Wie sieht hier der Algorithmus aus, um alle notwendigen 4er-Beziehungen zu erzeugen, welche wiederum alle möglichen Zeichenpaare enthalten? Wie kann man auch möglichst Wiederholungen vermeiden?

Now it becomes difficult…
Die gleiche Situation wie vor, nur stehen nun jeweils fünf Zeichen auf einer Zeile. Damit sind pro Zeile 10 Varianten der Zahlenpaare enthalten (wieder das Beispiel „ABCDE“ = „AB“, „AC“, „AD“, „AE“, „BC“, „BD“, „BE“, „CD“, „CE“ und „DE“ - nicht vergessen: es geht bislang aber immernoch um die 11 Zeichen bis K!)

And now the final shoot…
Jetzt wollen wir die ganze Angelegenheit flexibel machen.
Flexibel bedeutet, dass wir uns 1. nicht auf 11 Zeichen beschränken wollen, 2. auch nicht nur auf Zeichenpaare und 3. auch die Anzahl der Zeichen pro Zeile frei wählbar ist…

  1. Aufgabe: Wie ermitteln wir
    a) mathematisch:
    wieviele Zeilen (Z) mindestens nötig sind (Wiederholungen ausschließbar?), um
    alle Varianten (V)
    mit (A) Anzahl vorgegebener Zeichen (also 2, 3, … n)
    von insgesamt (S) gegebenen Zeichen (also n+1,…, S-1)
    zu berechnen und

b) logisch (programmtechnisch),
um diese gesuchten Varianten zu erzeugen und auszugeben? Wie kann man die Sache so optimieren, dass die Anzahl der Wiederholungen so gering als möglich ist?

Ich möchte dieses theoretische Problem gern am Computer lösen und brauchte Formeln und Algorithmen dazu…

#2

Hallo,

also sehr viel kann ich dir nicht weiterhelfen.
Aber du hast geschrieben das du als 11 Zeichen ( Buchstaben) = 55 Paare bekommst?
Entweder habe ich gerade ein Denkfehler :frowning: oder du irrst dich.
Bei mir sind es wenn du 11 Zeichen hast, 66 Paare.

Soweit ich mich noch erinnere nimmst du die Zeichenanzahl und addierst dann alle Zahlen zusammen.
Also:

11 Zeichen -> 11+10+9+8+7+6+5+4+3+2+1 = 66 Paare

Praktisches Bsp.

4 Buchstaben : ABCD
Mögliche Paare : AA,AB,AC,AD,BB,BC,BD,CC,CD,DD = 10 Paare
Rechenweg: 4+3+2+1 =10

3 Buchstaben: ABC
Mögliche Paare: AA,AB,AC,BB,BC,CC = 6 Paare
Rechenweg: 3+2+1=6

Habe ich derzeit einen argen Denkfehler oder irre ich mich maechtig gewaltig?
Wie bist du denn auf die 55 gekommen?

MFG Alex

#3

Na also ein Denkfehler ist es weniger. Vielleicht eher a bissel schwach beschrieben von mir…

55 Paare sind es, wenn jedes Zeichen sich mit einem ANDEREM PAART. Ein „A“ zb. kann sich nicht mit sich selber paaren („AA“=nicht möglich)

Die Formel aus der Kombinatorik lautet „n über k“, wobei n die Anzahl der Zeichen und k die Menge der daraus zu kombinierenden Zeichen sind. Unsere Aufgabenstellung hier ist also 11 über 2 und ausgeschrieben sieht das so aus: n!/k!(n-k)! (n Fakultät durch k Fakultät mal (n-k) Fakultät). ABer das nur am Rande…

Grüße, Uwe

#4

Hallo,

Ich möchte dieses theoretische Problem gern am Computer lösen
und brauchte Formeln und Algorithmen dazu…

beim Berechnen kann ich Dir nicht helfen, aber ein VB-Programm, das Kombinationen aus einer Elementeliste erstellt, war kein Problem.
Mail mit Quellcode ist unterwegs.

Gruß, Rainer

#5

Quellcode angekommen, Problem nicht gelöst
Hallo Rainer,

danke für Deine Bemühungen :smile:
Das Programm von Dir löst leider die Aufgabenstellung (noch) nicht.
Bestimmt habe ich mich nur zu ungenau ausgedrückt. Von daher beschreibe ich das Problem nochmals:

Also, die Kombinationen aus X Zeichen (jetzt der Einfachheit halber mal nur mit 6 Zeichen demonstriert) ist noch relativ einfach. Bleiben wir mal bei Paaren. Aus den 6 Zeichen: A, B, C, D, E und F lassen sich (lt. Formel 6 über 2) 15 Paare bilden. Diese sind:

  1. AB
  2. AC
  3. AD
  4. AE
  5. AF
  6. BC
  7. BD
  8. BE
  9. BF
  10. CD
  11. CE
  12. CF
  13. DE
  14. DF
  15. EF
    Bis hierher alles klar. Diese „Liste“, bestehend aus 15 Elementen auf 15 Zeilen möchte ich nun „verbauen“, und zwar so, dass die Anzahl der Zeichen pro Zeile gleich 3 ist (in der fortgeschritteneren Stufe sollen es dann auch vier oder n-1 Zeichen sein).
    Also schreibe ich auf die neue erste Zeile
  16. ABC
    Darin enthalten sind die Elemente AB, AC und BC
    Nun streiche ich quasi aus meiner vorhergehenden Liste die Zeilen 1,2 und 6 weg. Die nächste neue Zeile 2 ist meinetwegen
  17. ADE
    Darin „verbaut“ sind die Elemente AD, AE und DE
    Also streichen wir auch diese aus der vorhergehenden Liste weg (Zeilen 3, 4 und 13).

Und so weiter und so fort. Ich möchte nun wissen, wieviele Zeilen die neue Liste enthält. Nun ist die Aufgabenstellung bei 6 Zeichen und Paaren noch relativ überschaubar. Daher als nächstes die fortgeschrittenere Stufe: 4 Zeichen pro Zeile auf der neuen Liste!
1 Zeile: ABCD (enthält AB, AC, AD, BC, BD und CD = die Zeilen 1, 2, 3, 6, 7 und 10 der ursprünglichen Liste)
Die Aufgabe ist also, die ursprünglichen Elemente „platzsparend“ ineinander zu falten. In Deinem Programm hast Du die Paare lediglich nebeneinander gesetzt (ABAC ist aber nicht das Ziel). Problem erkannt?
Die nächste Zeile müsste nun eigentlich mit AE beginnen und dann müssten wir das BF verbauen
2. Zeile ABEF (enthält AB, AE, AF, BE, BF und EF, das sind die Zeilen 1, 4, 5, 8, 9 und 15) Uns fällt auf, dass das Element AB doppelt vorhanden scheint. Merken!
Nun haben wir nur noch die Zeilen 11-14, also die Elemente CE, CF, DE und DF übrig. Daher
3. Zeile CDEF (enthält CD, CE, CF, DE, DF und EF, also Zeilen 10, 11, 12, 13, 14 und 15).
Ich glaube, dass dies die kleinste mögliche Verschachtelung ist. Dennoch haben wir die Elemente AB, CD und EF dopelt verwenden müssen. Der Grund ist glaube ich klar: 15 Ausgangspaare zu 6er Paaren (ergeben sich ja, wenn man statt 2 nun 4 Zeichen pro Zeile zulässt) geht nicht gerade auf. 15 / 6 = 2, Rest 3. Daraus folgt, dass wir für die vollständige Verbauung aller Paare 3 Paare übrig haben und somit 3 Paare doppelt benutzen müssen.

Mathematisch sollten wir also ableiten können, dass die Anzahl der benötigten Zeilen (Z) sich ergibt aus der Menge der ursprünglichen Kombinationen (K) geteilt drch die Menge der Kombinationen (M) pro Zeile. Bei 6 Ausgangszeichen als Paare ergeben sich demnach 15 Zeilen, geteilt durch die neue Kombinationsmenge 6 (weil nun 4 Zeichen pro Zeile) haben wir also 3 Zeilen.

Wie sieht es nun aber aus, wenn wir 50 statt 6 Zeichen hätten und diese erst in Kombinationen zu 5 Zeichen ordnen (sind 2.118.760 Kombinationen) und diese dann in Zeilen zu jeweils 10 Zeichen (sind dann jewels 252 Kombinationen pro Zeile) ausgeben? Rein rechnerisch erhalten wir also 2.118.760 / 252 = 8.408 Zeilen. Nur wie sehen die aus? Rein rechnerisch brauchen wir weiterhin 56 5er-Kombinationen doppelt, um alle Kombinationen zu falten.
Hier suche ich also ein Programm, welchem ich erstens die Parameter eingeben kann (Gesamtmenge Zeichen oder Zahlen, 1. Kombinationsbreite, 2. Kombinationsbreite) und welches mir 2. die einzelnen Kombinationen optimiert (also nur so viele Doppelvorkommen einzelner Kombinationen, wie rechnerisch nötig sind) ausgibt.

Dann hoffe ich, dass es einen klügeren Kopf als mich gibt, der mir hier weiterhelfen kann. Dem ersten, der mir hierfür einen Algorithmus gibt, schenke ich 50 Euro. Bedingung: Es dürfen wirklich nicht mehr Zeilen als rechnerisch ermittelt ausgegeben werden und alle Kombinationen müssen vorkommen. Also, wo sind die Knobler und Tüftler unter Euch?

Gruß Uwe

#6

Noch mal hallo,

die Mail ist zurück gekommen. Unser Server hat sie nicht ‚durchgelassen‘. :wink:

Also dann der Quellcode so, mußt Du die Form dazu selbst ‚basteln‘.

Option Explicit

Dim Pos(20) As Integer
Dim i, n, k, Pointer, Anz\_KE, Anz\_Elem As Long
Dim zl, w As String

Private Sub Command1\_Click()
 List2.Visible = False
 Anz\_Elem = List1.ListCount
 Anz\_KE = Val(Text2.Text)
 
 For i = 0 To Anz\_KE - 1
 Pos(i) = i
 Next
 
 Do While Not Pos(0) \> Anz\_Elem - Anz\_KE
 zl = ""
 For i = 0 To Anz\_KE - 1
 w = List1.List(Pos(i))
 zl = zl & w
 Next
 List2.AddItem zl
 n = n + 1

 Pos(Anz\_KE - 1) = Pos(Anz\_KE - 1) + 1

 If Pos(Anz\_KE - 1) \>= Anz\_Elem Then
 Pointer = Anz\_KE - 1
 Do While Pos(Anz\_KE - 1) \>= Anz\_Elem
 Pointer = Pointer - 1
 If Pointer Anz\_Elem - Anz\_KE
 zl = ""
 For i = 0 To Anz\_KE - 1
 w = List1.List(Pos(i))
 zl = zl & w
 Next
 List2.AddItem zl
 n = n + 1

 Pos(Anz\_KE - 1) = Pos(Anz\_KE - 1) + 1

 If Pos(Anz\_KE - 1) \>= Anz\_Elem Then
 Pointer = Anz\_KE - 1
 Do While Pos(Anz\_KE - 1) \>= Anz\_Elem
 Pointer = Pointer - 1
 If Pointer 

Das sind nur zwei Listen, drei Textfleder, drei Buttons und ein paar Label, die aber unwichtig sind.

Wenn etwas unklar ist, mußt Du fragen.

Gruß, Rainer
#7

Hi,

… aahhhh, ja. Ich glaube ich durchschaue allmählich Dein Ziel. :wink:

Du willst ein Programm, das Dir eine Lottoreihe so aufbaut, daß z.B. ein Dreier garantiert ist, jede mögliche Dreier-Kombination enthält. … oder eben auch für Vierer, Fünfer … es müssen immer sechs Zahlen angekreuzt werden, es soll aber kein vollmathematisches System für eine Sechser entstehen, sondern nur ein System, das Dir einen Dreier, Vierer… garantiert. … für einen bestimmten, optimalen Bereich.
Verstanden, sehe ich mir noch nal näher an.
Hättest Du das gleich gesagt, wär’s einfacher gewesen, als mit erraten.

Gruß, Rainer

#8

Der Quelltext hatte mich per Mail erreicht. Habe auch schon hier im Forum geantwortet…

Gruß Uwe