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
    4. Public Structure Range
    5. Implements IEquatable(Of Range)
    6. Public Property First As Integer
    7. Public Property Last As Integer
    8. Public Overrides Function ToString() As String
    9. Return String.Format("[{0}, {1}]", First, Last)
    10. End Function
    11. Public Overrides Function GetHashCode() As Integer
    12. Return First Xor Last
    13. End Function
    14. Public Overrides Function Equals(obj As Object) As Boolean
    15. Return obj IsNot Nothing AndAlso TypeOf obj Is Range AndAlso Equals(DirectCast(obj, Range))
    16. End Function
    17. Public Sub New(first As Integer, last As Integer)
    18. Me.First = first
    19. Me.Last = last
    20. End Sub
    21. Public Overloads Function Equals(other As Range) As Boolean Implements IEquatable(Of Range).Equals
    22. Return First = other.First AndAlso Last = other.Last
    23. End Function
    24. End Structure
    25. Private NotInheritable Class RangesEnumerable
    26. Implements IEnumerable(Of Integer())
    27. Private _ranges As Range()
    28. Public Sub New(ranges As Range())
    29. If ranges Is Nothing Then Throw New ArgumentNullException("ranges")
    30. _ranges = ranges
    31. End Sub
    32. Public Function GetEnumerator() As IEnumerator(Of Integer()) Implements IEnumerable(Of Integer()).GetEnumerator
    33. Return New RangesEnumerator(_ranges)
    34. End Function
    35. Private Function GetEnumeratorObj() As IEnumerator Implements IEnumerable.GetEnumerator
    36. Return GetEnumerator()
    37. End Function
    38. End Class
    39. Private NotInheritable Class RangesEnumerator
    40. Implements IEnumerator(Of Integer())
    41. Private _state As EnumeratorState
    42. Private _current() As Integer
    43. Private _ranges() As Range
    44. Public Sub New(ranges() As Range)
    45. _ranges = DirectCast(ranges.Clone(), Range())
    46. Reset()
    47. End Sub
    48. Public ReadOnly Property Current As Integer() Implements IEnumerator(Of Integer()).Current
    49. Get
    50. If _state = EnumeratorState.Disposed Then
    51. Throw New ObjectDisposedException(GetType(IEnumerator(Of Integer())).Name)
    52. ElseIf _state = EnumeratorState.Ended Then
    53. Throw New ArgumentException("Enumerator has already ended.")
    54. ElseIf _state = EnumeratorState.Reset Then
    55. Throw New ArgumentException("Enumerator has not been started.")
    56. End If
    57. Return DirectCast(_current.Clone(), Integer())
    58. End Get
    59. End Property
    60. Private ReadOnly Property CurrentObj As Object Implements IEnumerator.Current
    61. Get
    62. Return Current
    63. End Get
    64. End Property
    65. Public Function MoveNext() As Boolean Implements IEnumerator.MoveNext
    66. If _state = EnumeratorState.Disposed Then Throw New ObjectDisposedException(GetType(IEnumerator(Of Integer())).Name)
    67. If _state = EnumeratorState.Ended Then
    68. Return False
    69. End If
    70. If _state = EnumeratorState.Reset Then
    71. 'Anfangswerte übernehmen, wenn dies der erste Aufruf an den Enumerator ist
    72. Dim cr(_ranges.Length - 1) As Integer
    73. For i As Integer = 0 To _ranges.Length - 1
    74. cr(i) = _ranges(i).First
    75. Next
    76. _current = cr
    77. _state = EnumeratorState.Running
    78. Else
    79. Dim inc As Boolean = False
    80. 'Von hinten nach vorne hochzählen. Wenn der Maximalwert erreicht wurde, wird wieder der Anfangswert übernommen und der nächste hochgezählt
    81. For i As Integer = _current.Length - 1 To 0 Step -1
    82. Dim r As Range = _ranges(i)
    83. 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)
    84. Dim ci As Integer = _current(i)
    85. If r.Last * cs > ci * cs Then
    86. _current(i) += cs
    87. inc = True
    88. Exit For
    89. Else
    90. _current(i) = r.First
    91. End If
    92. Next
    93. If Not inc Then _state = EnumeratorState.Ended
    94. End If
    95. Return Not _state = EnumeratorState.Ended
    96. End Function
    97. Public Sub Reset() Implements IEnumerator.Reset
    98. If _state = EnumeratorState.Disposed Then Throw New ObjectDisposedException(GetType(IEnumerator(Of Integer())).Name)
    99. _state = EnumeratorState.Reset
    100. _current = Nothing
    101. End Sub
    102. Public Sub Dispose() Implements IDisposable.Dispose
    103. _state = EnumeratorState.Disposed
    104. End Sub
    105. Private Enum EnumeratorState
    106. Disposed = -3
    107. Ended = -2
    108. Reset = -1
    109. Running = 0
    110. End Enum
    111. 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
    2. Public Values As New List(Of Value)
    3. Public Function HasNext() As Boolean
    4. For Each v In Values
    5. If v.HasNext Then Return True
    6. Next
    7. Return False
    8. End Function
    9. Public Sub NextStep()
    10. Dim übertrag As Boolean = True
    11. Dim current As Value
    12. For i = Values.Count - 1 To 0 Step -1 'eigentlich nicht notwendig
    13. current = Values(i)
    14. If übertrag Then
    15. übertrag = Not current.HasNext
    16. current.NextStep()
    17. End If
    18. Next
    19. End Sub
    20. Public Function getValues() As Integer()
    21. Dim tmp As New List(Of Integer)
    22. For Each v In Values
    23. tmp.Add(v.Wert)
    24. Next
    25. Return tmp.ToArray
    26. End Function
    27. End Class
    28. Public Class Value
    29. Public Wert As Integer
    30. Public Min As Integer
    31. Public Max As Integer
    32. Public Function HasNext() As Boolean
    33. Return Wert < Max
    34. End Function
    35. Public Sub NextStep()
    36. Wert += 1
    37. If Wert > Max Then Wert = Min
    38. End Sub
    39. End Class


    Visual Basic-Quellcode

    1. Public Class Form1
    2. Private Sub Form1_Shown(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Shown
    3. Dim p As New PermutationGenerator
    4. For i = 1 To 3
    5. p.Values.Add(New Value With {.Min = 0, .Max = 1, .Wert = 0})
    6. Next
    7. Do
    8. Console.WriteLine(String.Join(",", p.getValues)) 'Ausgabe
    9. If Not p.HasNext Then Exit Do 'Wenn Ende erreicht aufhören
    10. p.NextStep() 'Nächsten Schritt
    11. Loop
    12. End Sub
    13. 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
    2. ReDim myArray(0, 2), Max(2)
    3. Max(0) = 5
    4. Max(1) = 3
    5. Max(2) = 4
    6. Do
    7. For i = LBound(myArray, 2) To UBound(myArray, 2)
    8. Debug.Print myArray(0, i);
    9. Next i
    10. Debug.Print
    11. For i = LBound(myArray, 2) To UBound(myArray, 2)
    12. myArray(0, i) = myArray(0, i) + 1
    13. If myArray(0, i) <= Max(i) Then Exit For
    14. myArray(0, i) = 0
    15. If i = UBound(myArray, 2) Then Exit Do
    16. Next i
    17. Loop
    Gruss,

    Neptun