1. Herfried K. Wagner’s VB.Any
  2. Visual Basic
  3. Code

Algorithmen

Prüfen, ob eine Summe eine Lösung eines MSA-Problems darstellt

Die Prozedur IsSumSolution überprüft, ob eine in einer Zeichenfolge übergebene Summe von Sequenzen eine gültige Lösung eines MSA-Problems darstellt.

Unter der Summe mehrerer Ketten verstehen wir jene Kette z, die sich durch elementweise Kombination aus zwei Ketten ergibt. Die Ketten müssen so beschaffen sein, daß es nicht vorkommt, daß alle Ketten an einer Stelle nur Leerzeichen „-“ besitzen. Außerdem dürfen keine unterschiedlichen Zeichen in einer Spalte der Matrix stehen, wenn man sich die Ketten als Matrix untereinander geschrieben vorstellt. Die Ketten müssen alle die gleiche Länge besitzen. Im folgenden Beispiel wird gezeigt, wie man die Summe von drei Ketten bildet. Auf eine formale Definition wird aufgrund der Trivialität dieses Problems verzichtet:

ACGGCAC-ACC-GCA--C
AC-GCA--AC-GGCA-TC   =>   ACGGCAGTACCGGCATTC
AC---A-T-CCGGC-TTC

Eine Implementierung könnte folgendermaßen aussehen:

Private Sub Main()
    
    ' Beispieleingabeinstanz erstellen.
    Dim s(0 To 4) As String
    s(0) = "ACA"
    s(1) = "ACA"
    s(2) = "ACA"
    s(3) = "ACA"
    s(4) = "ABC"
    
    ' Prüfen, ob die angegebene Zeichenfolge die Summe einer Lösung des
    ' Problems darstellt.
    Call MsgBox(IsSumSolution("ACACB", s))  ' 'False'.
    Call MsgBox(IsSumSolution("ABCA", s))   ' 'True'.
End Sub

'
' Ermittelt, ob es sich bei der Summe in 'SumOfSolution' um eine Lösung des
' Problems in 'ProblemSequences' handelt.
'
Private Function IsSumSolution( _
    ByVal SumOfSolution As String, _
    ByRef ProblemSequences() As String _
) As Boolean
    Dim i As Long, j As Long, k As Long, g As String * 1
    
    ' Einen Eingabestring nach dem anderen testen.
    For i = 0 To UBound(ProblemSequences)
        j = 1   ' Position in der Folge in 'ProblemSequences'.
        k = 1   ' Position in der Summe.
        
        ' Zeichenweise Eingabetext durchgehen und in Summe weitersuchen.
        Do While j <= Len(ProblemSequences(i))
            
            ' 'j'-tes Zeichen aus Eingabetext nehmen.
            g = Mid$(ProblemSequences(i), j, 1)
            
            Do
                
                ' Wenn die Summe zu kurz ist, kann dies keine Lösung mehr
                ' sein, d.h. es sind noch nicht alle Zeichen der
                ' Eingangskette zur Deckung gebracht, aber in der Summe
                ' gibt es keine Ketten mehr.
                If k > Len(SumOfSolution) Then
                    Exit Function   ' <-- 'Return False'.
                
                ' Wenn nun nach der aktuellen Position in der Summe weniger
                ' Zeichen sind, als noch im Quelltext ab der aktuellen
                ' Position sind, dann kann es keine Lösung sein.
                ElseIf _
                    Len(SumOfSolution) - k < _
                    Len(ProblemSequences(i)) - j _
                Then
                    Exit Function   ' <-- 'Return False'.
                
                ' Es besteht noch weiterhin die Möglichkeit, daß dies eine
                ' Lösung ist.
                Else
                    If Mid$(SumOfSolution, k, 1) <> g Then
                        k = k + 1
                    Else
                        k = k + 1
                        Exit Do
                    End If
                End If
            Loop
            j = j + 1   ' Nächstes Zeichen der Eingabekette.
        Loop
    Next i
    IsSumSolution = True
End Function

Prüfen, ob eine Summe eine Lösung eines MSA-Problems darstellt.