Algorithmus für Kombinationen

Roman Locher

Mitglied
Ich möchte für eine beliebige Anzahl von vorgegebenen Werten, alle möglichen Kombinationen ermitteln. Also z.B. für 4 Werte alle möglichen 1er,2er,3er und 4er Paare.

Ergebnis müsste dann ungefähr so aussehen:

1; 2; 3; 4
1_2; 1_3; 1_4; 2_3; 2_4; 3_4
1_2_3; 1_2_3; 1_3_4; 2_3_4
1_2_3_4

Für die 2er Paare bekomm ich's noch einfach hin - aber für alle Kombinationen hab ich grad keine Idee.
 
Unter dem Stichwort Permutation findet ja man schon einiges. Aber es wird immer davon ausgegangen, dass ich bei 3 Werten auch immer 3er Kombinationen haben möchte. Ich brauche aber auch alle 1er, 2er Kombinationen.
 
Bin etwas weiter gekommen, ist aber nicht 100%

PHP:
Public Function Test()
    Dim wert(1 To 5), i As Integer, max As Integer, y As Integer, start As Integer, x As Integer, y_ As Integer, z As Integer, z_ As Integer, max_ As Integer
    
    wert(1) = 1
    wert(2) = 2
    wert(3) = 3
    wert(4) = 4
    wert(5) = 5
    max = 5
    
    For x = 1 To (max - 2)
        For i = 1 To (max - 1)
            max_ = max
            If (i + x) > max Then
                max_ = max + x - 1
            End If
            For y = (i + x) To (max_)
                y_ = y
                If y > max Then
                    y_ = y - max
                End If
                    For z = i To (i + x - 1)
                        z_ = z
                        If z > max Then
                            z_ = z - max
                        End If
                        Debug.Print wert(z_)
                    Next z
                Debug.Print wert(y_)
            Debug.Print "#"
            Next y
            Debug.Print "#"
        Next i
    Next x
    
    
    
End Function
 
Hallo Roman,

Wenn die Menge der Elemente die gefunden werden soll immer gleich ist, ist das Verfahren einfach. Für 3 Elemente sieht es z. B. so aus:

Code:
Sub Kombinationen_3()
  'Beispiel für 3 Element aus der Menge 'Wert()'
  
  Dim iUG As Integer                    ' untere Array Grenze
  Dim iOG As Integer                    ' obere Array Grenze
  Dim iZahler_1 As Integer              ' Zähler
  Dim iZahler_2 As Integer              ' Zähler
  Dim iZahler_3 As Integer              ' Zähler
  
  Dim wert(1 To 5) As Integer
    wert(1) = 1
    wert(2) = 2
    wert(3) = 3
    wert(4) = 4
    wert(5) = 5
  
  iUG = LBound(wert())
  iOG = UBound(wert())
  For iZahler_1 = iUG To iOG
    For iZahler_2 = iZahler_1 + 1 To iOG
      For iZahler_3 = iZahler_2 + 1 To iOG
        Debug.Print wert(iZahler_1), wert(iZahler_2), wert(iZahler_3)
      Next iZahler_3
    Next iZahler_2
  Next iZahler_1
End Sub

Dieses Verfahren ist leider nicht flexibel. Für eine andere Anzahl Elemente muss die Prozedur geändert werden.
Ob ich einen allgemeingütigen Algorithmus (n Element aus einer Menge m) hinbekomme versuche ich noch.

Viel Erfolg
Walter Gutermann
 
Hallo Roman,

das war eine schöne Aufgabe. Hier nun meine Vorstellung von einem universellen Algorithmus:

Anzahl der Kombinationen non N Elementen aus einer Menge von M Elementen (ohne Wiederholung).

- Initiiere Anfangspositionen
(pos(1) = 1; pos(2) = 2; ….pos(N) = N)

- Start der Schleife

- iStart = pos(N – 1), = vorletzte Position

- Erhöhe Position letztes Element pos(N) = iStart +1 bis M
pos(N) = iStart +1
pos(N) = iStart + 2
bis
pos(N) = M

--> hier Ausgabe der Werte

- Stelle fest wie viel Elemente ihre Endposition erreicht haben
= iAnzEndPos

- erhöhe Element (N – iAnzEndPos) um 1

- Aktualisiere die Positionen der nachfolgenden Elementen von
Element (N – iAnzEndPos). Jedes nachfolgende Element ist um 1 höher als sein Vorgänger.
pos(N – iAnzEndPos + 1) = pos(N – iAnzEndPos ) + 1
bis
pos(N) = pos(N – 1) + 1

- Tue das so lange, bis alle Elemente ihre Endposition erreicht haben
(iAnzEndPos = N)


Bitte melde Dich wenn Du den Algorithmus umgesetzt hast.

Viel Erfolg
Walter Gutermann

NS: In meiner ersten Antwort habe ich noch einen Schönheitsfehler entdeckt. Die beiden äußere Schleifen machen einige Null - Durchgänge. Das Schleifenende kann um 2 bzw. 1 gekürzt werden.
 
Hi,
die schnellste Variante ist folgende:
Code:
Dim a As Integer, b As Integer, c As Integer, d As Integer, e As Integer, f As Integer
Dim  n As Long
n = 0

For a = 1 To 1
  For b = a + 1 To 2
    For c = b + 1 To 3
      For d = c + 1 To 4
        For e = d + 1 To 5
            n = n + 1
          Next e
        Next d
      Next c
    Next b
  Next a
Die 2er Kombination ergibt 10 Möglichkeiten ohne Wiederholung.
Welche Kombinationen o.W. Du auch immer suchst, in Excel kannst Du die Anzahl der Möglichkeiten relativ leicht ermitteln.
Grüße
 
Hi, natürlich. Seit einiger Zeit schon!
Grüße
PS.: Das ist nur das Grundgerüst. Das Schreiben in einer Datei etc. fehlt natürlich und es werden ALLE Kombinationen aus den Zahlen 1 - 5 generiert. Wenn Du allerdings die Auswahlzahlen selbst definieren möchtest, dann ist diese Variante nicht zutreffend.
 
Hallo Alfred,

in Deinem Beispiel wird jede Schleife genau 1mal durchlaufen (Schleife a von 1 nach 1, Schleife b von 2 nach 2, …). Das Ergebnis ist, dass n von 0 auf 1 erhöht wird. Mehr geschieht nicht.

Grüße
Walter Gutermann
 
Hi,
Deine Kritik zu DIESEM Beispiel ist richtig. Ich wollte Dir nur das Grundgerüst vermitteln.
Der Code 5aus2 muss lauten!
Code:
For a = 1 To 4
  For b = a + 1 To 5
   n = n + 1
  Next b
 Next a
Solltest Du 6aus49 mit 13,983.816 Kombinationen o.W.
generieren wollen, dann geht das so:
Code:
For a = 1 To 44
  For b = a + 1 To 45
    For c = b + 1 To 46
      For d = c + 1 To 47
        For e = d + 1 To 48
          For f = e + 1 To 49
            n = n + 1
            Next f
          Next e
        Next d
      Next c
    Next b
  Next a
Eine schnellere Routine ist mir nicht bekannt. Alles klar?
Grüße
 
Zurück