Die Community zu .NET und Classic VB.

Startseite / Tipps / VB.NET-Tipp 0095: IEnumerable implementieren - Array permutieren

VB.NET-Tipp 0095: IEnumerable implementieren - Array permutieren

 von Spatzenkanonier

Schwierigkeitsgrad:

Framework-Version(en): .NET Framework 2.0, .NET Framework 3.0, .NET Framework 3.5

.NET-Version(en): Visual Basic 2005, Visual Basic 2008

Download: Download des Beispielprojektes [9,48 KB]

' Dieser Quellcode stammt von http://www.activevb.de
' und kann frei verwendet werden. Für eventuelle Schäden
' wird nicht gehaftet.

' Um Fehler oder Fragen zu klären, nutzen Sie bitte unser Forum.
' Ansonsten viel Spaß und Erfolg mit diesem Source!

' Projektversion:   Visual Studio 2005
' Option Strict:    An
'
' Referenzen: 
'  - System
'  - System.Data
'  - System.Xml
'
' Imports: 
'  - Microsoft.VisualBasic
'  - Microsoft.VisualBasic.ControlChars
'  - System
'  - System.Collections
'  - System.Collections.Generic
'  - System.Data
'  - System.Diagnostics
'

' ##############################################################################
' ################################ modMain.vb ##################################
' ##############################################################################
Public Module modMain
    Public Sub Main()
        ' Einfacher kann man wohl nicht permutieren
        For Each Mutation As String() In _
            Permutations.Of("ant", "bat", "cow", "dog")

            Console.WriteLine(String.Join(" ", Mutation))
        Next
        Console.ReadLine()
    End Sub
End Module

' ##############################################################################
' ############################## Permutations.vb ###############################
' ##############################################################################
Imports System.Collections

Public Class Permutations
    ''' <summary>
    ''' Ermittelt durch Rückschluss den Type-Parameter, sodass man ihn nicht mal 
    ''' anzugeben braucht
    ''' </summary>
    Public Shared Function [Of](Of T)( _
            ByVal ParamArray InitArray As T()) As Permutations(Of T)
        Return New Permutations(Of T)(InitArray)
    End Function
End Class 'Permutations

''' <summary>
''' erzeugt einen Enumerator zur Permutation von Arrays beliebigen Types, 
''' verwendbar in ForEach-Schleifen
''' </summary>
Public Class Permutations(Of T) : Implements IEnumerable

    Private _InitArray As T()

    Public Sub New(ByVal InitArray As T())
        _InitArray = InitArray
    End Sub

    Public Function GetEnumerator() As IEnumerator _
        Implements IEnumerable.GetEnumerator

        Return New Enumerator(_InitArray)
    End Function

    Public Class Enumerator : Implements IEnumerator
        ' Das Implementieren von IEnumerable zieht direkt ein Implementieren 
        ' von IEnumerator nach sich; ist IEnumerable doch nix anderes als eine 
        ' "factory" für Enumeratoren
        Private _InitArray As T()
        ' Die Indizes werden permutiert
        Private _Indices As Integer()

        Friend Sub New(ByVal InitArray As T())
            _InitArray = InitArray
        End Sub

      Public Sub Reset() Implements IEnumerator.Reset
         ' Eigentümlicherweise wird dieser Schnittstellenmember nie verwendet
      End Sub

        Public ReadOnly Property Current() As Object _
            Implements IEnumerator.Current

            Get
                Dim UBound As Integer = _InitArray.Length - 1
                Dim RetVal(UBound) As T

                '_InitArray mit umgestellter Reihenfolge nach RetVal kopieren
                For I As Integer = 0 To UBound
                    RetVal(I) = _InitArray(_Indices(I))
                Next
                Return RetVal
            End Get
        End Property

        ''' <summary>
        ''' Berechntet aus der vorherigen Permutation die nächste
        ''' </summary>
        ''' <remarks>Die neue Permutation ist als Current() abrufbar</remarks>
        Public Function MoveNext() As Boolean Implements IEnumerator.MoveNext
            Dim UBound As Integer = _InitArray.Length - 1
            If _Indices Is Nothing Then
                ' Indizes-Startwerte: 0,1,2,3,4...
                ReDim _Indices(UBound)
                For I As Integer = 0 To UBound
                    _Indices(I) = I
                Next
                ' Mehr ist beim Erstaufruf nicht zu tun
                Return UBound > 0
            End If

            ' Indicees permutieren. 
            ' Es wird ein linker und ein rechter Wert gesucht, die vertauscht 
            ' werden. Anschließend die Reihenfolge rechts vom Links-Wert 
            ' umkehren
            Dim Left As Integer, Right As Integer

            ' Links-Wert: muss kleiner sein als sein rechter Nachbar
            For Left = UBound - 1 To 0 Step -1
                If _Indices(Left) < _Indices(Left + 1) Then Exit For
            Next
            If Left < 0 Then
                ' Eine weitere Permutation kann nicht berechnet werden
                _Indices = Nothing '_Indices rücksetzen
                Return False
            End If
            Dim LeftVal As Integer = _Indices(Left)

            ' Rechts-Wert: größer als der Links-Wert 
            ' (ist nicht immer o.g. Nachbar!)
            For Right = UBound To 0 Step -1
                If _Indices(Right) > LeftVal Then Exit For
            Next

            ' Links-Wert und Rechts-Wert tauschen
            _Indices(Left) = _Indices(Right)
            _Indices(Right) = LeftVal

            ' Array rechts der Links-Position umkehren
            Array.Reverse(_Indices, Left + 1, UBound - Left)

            ' WriteLine(_Indices) ' Test-Ausgabe
            Return True
        End Function 'MoveNext
    End Class 'Permutations(Of T).Enumerator
End Class 'Permutations(Of T)