Feedback

VB - Permutation nachweisen

Veröffentlicht von am 11.03.2010
(2 Bewertungen)
Auf diese Weise lässt sich überprüfen, ob a eine Permutation von b ist.

http://de.wikipedia.org/wiki/Permutation

Function is_perm(ByVal a As String, ByVal b As String) As Boolean
    If a.Length <> b.Length Then Return False

    Dim ax, bx As Byte
    For Each c In a
        ax += CByte(Val(c))
    Next

    For Each c In b
        bx += CByte(Val(c))
    Next

    If ax <> bx Then Return False

    Dim al, bl As New ArrayList
    For Each c In a
        al.Add(c)
    Next
    al.Sort()

    For Each c In b
        bl.Add(c)
    Next
    bl.Sort()

    For x As Byte = 0 To al.Count - 1
        If al(x) <> bl(x) Then Return False
    Next

    Return True
End Function

6 Kommentare zum Snippet

Klemens Nanni schrieb am 15.04.2010:
Durch die Ergänzung in Zeile 8-13 wurde die Rechenzeit knapp halbiert. Denn stimmt die Quersumme nicht überein, brauchen wir gar nicht mit Listen arbeiten.
keco schrieb am 18.04.2010:
Hallo. Für übliche Wörter (<16 Zeichen) ist die Methode mit der Ergänzung aber sehr viel langsamer als ohne. Mit welchen Daten hast du das denn getestet?
Klemens Nanni schrieb am 20.04.2010:
Mit Zahlen, alle < 10^9, also nicht mehr als neun Zeichen.
Klemens Nanni schrieb am 20.04.2010:
Ja, da ich soetwas überwiegend für mathematische Dinge verwende, habe ich an die Anwendung auf Zeichketten weniger gedacht. Ich werde prüfen, ob es dadurch langsamer wird. Wenn ja, wird's verbessert.
keco schrieb am 21.04.2010:
Ich denke aber nicht, dass man mehrere Tausend Permuationen von extrem hohen Zahlen bzw. Zeichenketten mit vielen Zeichen berechnen muss. Bei den einigen Millisekunden kommt es da auch nicht drauf an. Bei 2 Methoden, die ich getestet habe gab es in den niedrigen Bereichen kaum Unterschiede und bei Zeichenketten mit 1000 Zeichen Unterschiede von 100 Millisekunden. Aber wer prüft so etwas auf Permutation?
Klemens Nanni schrieb am 21.04.2010:
Du hast Recht, sowetwas ist eher unüblich. Ich bin aber jemand, der immer versucht, den bestmöglichen Weg zu finden.
 

Logge dich ein, um hier zu kommentieren!