Elemente von Array kombinatorisch hochzählen

  • VB6

Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von brcktop.

    Elemente von Array kombinatorisch hochzählen

    Hallo zusammen

    Ich habe ein Array 1 x 3 Elemente.
    myArray (0, 2)

    Jedes Element hat einen eigenen Maximalwert, den ich vorher festlege.
    Z.B.
    Element2 bis 3,
    Element1 bis 2,
    Element0 bis 5.

    Nun sollen die Nullen jeweils einzeln hochgezält werden (beginnend bei ersten oder letzten Element, ist egal). Wenn sie den jeweiligen Maxwert erreicht haben, soll wieder auf Null gesetzt werden und in dem benachbarten
    Element
    um 1 hochgezählt werden. So sind alle Kombinationen dabei.

    Die ersten Schritte sind also (mit Maxwert von oben):
    0,0,0
    0,0,1
    0,0,2
    0,0,3
    0,1,0
    0,1,1
    0,1,2
    0,1,3
    0,2,0
    0,2,1
    0,2,2
    0,2,3
    1,0,0
    1,0,1
    ...
    5,2,3

    Wie kann man das programmiertechnisch machen? Kann es sein dass es nur mit einer rekursiven Funktion geht?
    Anfänglich würde mir auch eine Hilfe reichen, mit einem generellen Maxwert (für alle gleich). Vielleicht komm ich da schon weiter.

    Vielen Dank im Vorraus
    :rolleyes:

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „brcktop“ ()

    einfach 3 For-Schleifen ineinander verschachteln:

    Visual Basic-Quellcode

    1. For a = 0 To 1
    2. For b = 0 To 1
    3. For c = 0 To 1
    4. Console.WriteLine(a.ToString & b.ToString & c.ToString)
    5. Next
    6. Next
    7. Next


    erzeugt die Ausgabe:

    Quellcode

    1. 000
    2. 001
    3. 010
    4. 011
    5. 100
    6. 101
    7. 110
    8. 111

    Danke. Das ist die einfachste Möglichkeit. Ich hab vergessen zu schreiben, dass es sich bei der 1x3 Liste nur um ein Beispiel handelt. In Wirklichkeit sind es 10 bis 20 Werte. Das wird dann auch erst zur Laufzeit entschieden. Daher kann ich keine For Schleifen verschachtelt verwenden.
    Die Länge des Arrays muss man also für die Anzahl der Verschachtelungen abfragen. In meinem Beispiel war es 3.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „brcktop“ ()

    brcktop schrieb:

    Daher kann ich keine For Schleifen verschachtelt verwenden.
    Bei konstanter Anzahl der Elemente musst Du nur den Bereich entsprechend anpassen.
    Bei variabler Anzahl der Elemente solltest Du zunächst genau überlegen, was Du eigentlich willst, denn bei entsprechenden Randbedingungen dauert die Berechnung etwas länglich.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ja das mit dem Rechenaufwand hab ich bedacht. Es geht leider nicht anders. Ich mache schon alles im Array, damit es am schnellsten ist. Die Maxwerte sind aber eher klein (im Bereich von 1 bis 10). So hätte ich bei 10 Werten von durchschnittlich Maxwert=5 : 6 hoch 10 Loops. Ist hoch aber ich hab ja Zeit :)

    Ich würde eine Klasse für ein Element schreiben, mit den Eigenschaften Wert, Maximum und Minimum. Du kannst nun eine Liste von beliebig vielen Elementen erstellen (von denen alle Unterschiedliche Werte abdecken können). Um die nächste Permutationsfolge zu berechnen durchläufst du die Liste einfach und erhöhst das aktuelle Element um Eins. Erzeugt das einen 'Überlauf' (Wert > Maximum) setzt du ihn auf das Minimum und merkst dir, dass ein Überlauf stattgefunden hat. Das nächste Element erhöhst du um Eins, wenn das vorherige einen Überlauf erzeugte - ansonsten nicht. (Am besten die Liste rückwärts durchlaufen, das erzeugt die typische Ausgabe)

    Das wärs auch schon, in der Elemente-Liste kannst du nun die Werte auslesen. Eine nächste Permuationsfolge gibt es, wenn der Wert von mindestens einem Element nicht auf Maximum steht.

    Hab' da mal schnell was gebastelt:
    Spoiler anzeigen

    Visual Basic-Quellcode

    1. Public Shared Function EnumerateRanges(ranges As Range()) As IEnumerable(Of Integer())
    2. Return New RangesEnumerable(ranges)
    3. End Function
    5. Public Structure Range
    6. Implements IEquatable(Of Range)
    8. Public Property First As Integer
    9. Public Property Last As Integer
    11. Public Overrides Function ToString() As String
    12. Return String.Format("[{0}, {1}]", First, Last)
    13. End Function
    15. Public Overrides Function GetHashCode() As Integer
    16. Return First Xor Last
    17. End Function
    19. Public Overrides Function Equals(obj As Object) As Boolean
    20. Return obj IsNot Nothing AndAlso TypeOf obj Is Range AndAlso Equals(DirectCast(obj, Range))
    21. End Function
    23. Public Sub New(first As Integer, last As Integer)
    24. Me.First = first
    25. Me.Last = last
    26. End Sub
    28. Public Overloads Function Equals(other As Range) As Boolean Implements IEquatable(Of Range).Equals
    29. Return First = other.First AndAlso Last = other.Last
    30. End Function
    31. End Structure
    33. Private NotInheritable Class RangesEnumerable
    34. Implements IEnumerable(Of Integer())
    36. Private _ranges As Range()
    38. Public Sub New(ranges As Range())
    39. If ranges Is Nothing Then Throw New ArgumentNullException("ranges")
    40. _ranges = ranges
    41. End Sub
    43. Public Function GetEnumerator() As IEnumerator(Of Integer()) Implements IEnumerable(Of Integer()).GetEnumerator
    44. Return New RangesEnumerator(_ranges)
    45. End Function
    47. Private Function GetEnumeratorObj() As IEnumerator Implements IEnumerable.GetEnumerator
    48. Return GetEnumerator()
    49. End Function
    50. End Class
    52. Private NotInheritable Class RangesEnumerator
    53. Implements IEnumerator(Of Integer())
    55. Private _state As EnumeratorState
    56. Private _current() As Integer
    57. Private _ranges() As Range
    59. Public Sub New(ranges() As Range)
    60. _ranges = DirectCast(ranges.Clone(), Range())
    61. Reset()
    62. End Sub
    64. Public ReadOnly Property Current As Integer() Implements IEnumerator(Of Integer()).Current
    65. Get
    66. If _state = EnumeratorState.Disposed Then
    67. Throw New ObjectDisposedException(GetType(IEnumerator(Of Integer())).Name)
    68. ElseIf _state = EnumeratorState.Ended Then
    69. Throw New ArgumentException("Enumerator has already ended.")
    70. ElseIf _state = EnumeratorState.Reset Then
    71. Throw New ArgumentException("Enumerator has not been started.")
    72. End If
    73. Return DirectCast(_current.Clone(), Integer())
    74. End Get
    75. End Property
    77. Private ReadOnly Property CurrentObj As Object Implements IEnumerator.Current
    78. Get
    79. Return Current
    80. End Get
    81. End Property
    83. Public Function MoveNext() As Boolean Implements IEnumerator.MoveNext
    84. If _state = EnumeratorState.Disposed Then Throw New ObjectDisposedException(GetType(IEnumerator(Of Integer())).Name)
    85. If _state = EnumeratorState.Ended Then
    86. Return False
    87. End If
    88. If _state = EnumeratorState.Reset Then
    89. 'Anfangswerte übernehmen, wenn dies der erste Aufruf an den Enumerator ist
    90. Dim cr(_ranges.Length - 1) As Integer
    91. For i As Integer = 0 To _ranges.Length - 1
    92. cr(i) = _ranges(i).First
    93. Next
    94. _current = cr
    95. _state = EnumeratorState.Running
    96. Else
    97. Dim inc As Boolean = False
    98. 'Von hinten nach vorne hochzählen. Wenn der Maximalwert erreicht wurde, wird wieder der Anfangswert übernommen und der nächste hochgezählt
    99. For i As Integer = _current.Length - 1 To 0 Step -1
    100. Dim r As Range = _ranges(i)
    101. Dim cs As Integer = Math.Sign(r.Last - r.First) 'auch das Schrittvorzeichen beachten (z.B., wenn von 5 nach 0 gegangen werden soll, statt von 0 nach 5)
    102. Dim ci As Integer = _current(i)
    103. If r.Last * cs > ci * cs Then
    104. _current(i) += cs
    105. inc = True
    106. Exit For
    107. Else
    108. _current(i) = r.First
    109. End If
    110. Next
    111. If Not inc Then _state = EnumeratorState.Ended
    112. End If
    113. Return Not _state = EnumeratorState.Ended
    114. End Function
    116. Public Sub Reset() Implements IEnumerator.Reset
    117. If _state = EnumeratorState.Disposed Then Throw New ObjectDisposedException(GetType(IEnumerator(Of Integer())).Name)
    118. _state = EnumeratorState.Reset
    119. _current = Nothing
    120. End Sub
    122. Public Sub Dispose() Implements IDisposable.Dispose
    123. _state = EnumeratorState.Disposed
    124. End Sub
    126. Private Enum EnumeratorState
    127. Disposed = -3
    128. Ended = -2
    129. Reset = -1
    130. Running = 0
    131. End Enum
    132. End Class

    Das ganze berechnet nur dann die neuen Werte, wenn sie benötigt werden. Folgendes z.B. als Beispiel:

    Visual Basic-Quellcode

    1. Dim ranges() As Range = New Range() {New Range(2, 3), New Range(1, 2), New Range(0, 5)}
    2. Dim outp As New System.Text.StringBuilder()
    3. For Each di As Integer() In EnumerateRanges(ranges)
    4. outp.AppendLine(String.Join(", ", di))
    5. Next
    6. MessageBox.Show(outp.ToString())

    mit yield hätte man's übrigens auch machen können. Hätte mir dann auch ein paar Codezeilen erspart. ;)

    Gruß
    ~blaze~

    Das mit dem Enumerator ist schon cool xD Meins (ganz grob gehalten) sieht so aus:

    Visual Basic-Quellcode

    1. Public Class PermutationGenerator
    3. Public Values As New List(Of Value)
    5. Public Function HasNext() As Boolean
    6. For Each v In Values
    7. If v.HasNext Then Return True
    8. Next
    9. Return False
    10. End Function
    12. Public Sub NextStep()
    13. Dim übertrag As Boolean = True
    14. Dim current As Value
    15. For i = Values.Count - 1 To 0 Step -1 'eigentlich nicht notwendig
    16. current = Values(i)
    17. If übertrag Then
    18. übertrag = Not current.HasNext
    19. current.NextStep()
    20. End If
    21. Next
    22. End Sub
    24. Public Function getValues() As Integer()
    25. Dim tmp As New List(Of Integer)
    26. For Each v In Values
    27. tmp.Add(v.Wert)
    28. Next
    29. Return tmp.ToArray
    30. End Function
    32. End Class
    34. Public Class Value
    35. Public Wert As Integer
    36. Public Min As Integer
    37. Public Max As Integer
    39. Public Function HasNext() As Boolean
    40. Return Wert < Max
    41. End Function
    43. Public Sub NextStep()
    44. Wert += 1
    45. If Wert > Max Then Wert = Min
    46. End Sub
    48. End Class


    Visual Basic-Quellcode

    1. Public Class Form1
    3. Private Sub Form1_Shown(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Shown
    4. Dim p As New PermutationGenerator
    6. For i = 1 To 3
    7. p.Values.Add(New Value With {.Min = 0, .Max = 1, .Wert = 0})
    8. Next
    10. Do
    11. Console.WriteLine(String.Join(",", p.getValues)) 'Ausgabe
    12. If Not p.HasNext Then Exit Do 'Wenn Ende erreicht aufhören
    13. p.NextStep() 'Nächsten Schritt
    14. Loop
    16. End Sub
    18. End Class


    (Was mir bisher nie aufgefallen ist: der Zusatz 'Property' in der Value-Klasse kostet Faktor 2 in der Performance. Finde ich schon krass)

    Hallo brcktop,
    ist das VBA?
    Probier' mal dies:

    Visual Basic-Quellcode

    1. Dim i As Long, myArray() As Long, Max() As Long
    3. ReDim myArray(0, 2), Max(2)
    4. Max(0) = 5
    5. Max(1) = 3
    6. Max(2) = 4
    8. Do
    10. For i = LBound(myArray, 2) To UBound(myArray, 2)
    11. Debug.Print myArray(0, i);
    12. Next i
    13. Debug.Print
    15. For i = LBound(myArray, 2) To UBound(myArray, 2)
    16. myArray(0, i) = myArray(0, i) + 1
    17. If myArray(0, i) <= Max(i) Then Exit For
    18. myArray(0, i) = 0
    19. If i = UBound(myArray, 2) Then Exit Do
    20. Next i
    22. Loop
    Gruss,

    Neptun

Facebook
Telefonspende