Как заказать массив в лексикографическом порядке vb.net - PullRequest
Новая
       44

Как заказать массив в лексикографическом порядке vb.net

0 голосов
/ 06 декабря 2018

Это довольно сложно для меня, чтобы понять 

    Dim test() As Byte = New Byte() {50, 40, 30, 10, 10}
    Dim answer() As UInteger = SortLexicoGraphicallyBigIntegerArray(test)

Ответ - каждое вращение, отсортированное от наименьшего значения массива к наибольшему значению массива. 

Rotation 0 = 50, 40, 30, 10, 10
Rotation 1 = 10, 50, 40, 30, 10
Rotation 2 = 10, 10, 50, 40, 30
Rotation 3 = 30, 10, 10, 50, 40
Rotation 4 = 40, 30, 10, 10, 50

Когда я сортирую этот массиввыше, я должен получить 

Rotation 2 = 10, 10, 50, 40, 30
Rotation 1 = 10, 50, 40, 30, 10
Rotation 3 = 30, 10, 10, 50, 40
Rotation 4 = 40, 30, 10, 10, 50
Rotation 0 = 50, 40, 30, 10, 10

Таким образом, ответ должен быть 2, 1, 3, 4, 0

Я застрял в бесконечном цикле, и я не могу положить на него палец

Вот мой код 

Public Function GetRotation(Data As Byte(), rotation As UInteger) As Byte()
   'Rotation Left
    Dim rotationData As New List(Of Byte)

    Dim start As UInteger = Data.Length - rotation Mod Data.Length

    For i = 0 To Data.Length - 1
        rotationData.Add(Data((start + i) Mod (Data.Length)))
    Next

    Return rotationData.ToArray()
End Function

Public Function SortLexicoGraphicallyBigIntegerArray(data As Byte()) As UInteger()
    Dim OrderedRotations As New List(Of UInteger)
    Dim index As Integer = 0
    Dim rowSwapped As Boolean
    Dim data1 As Byte()
    Dim data2 As Byte()

    For rotation As Short = 0 To data.Length - 1
        OrderedRotations.Add(rotation)
    Next

    For rotation As Long = data.Length - 1 To 0 Step -1
        Do
            rowSwapped = False
            data1 = GetRotation(data, OrderedRotations(rotation))
            data2 = GetRotation(data, OrderedRotations((rotation + 1) Mod (data.Length)))
            Do
                If data1(index) > data2(index) Then
                    'Swaps a full row in a few copies.
                    Dim tmpFirst As UInteger = OrderedRotations(index)
                    OrderedRotations(index) = OrderedRotations(index + 1)
                    OrderedRotations(index + 1) = tmpFirst

                    data1 = GetRotation(data, OrderedRotations(rotation))
                    data2 = GetRotation(data, OrderedRotations((rotation + 1) Mod (data.Length)))
                    rowSwapped = True
                End If
                index += 1
            Loop While index < data.Length - 1
            index = 0

        Loop While rowSwapped <> False
    Next
    Return OrderedRotations.ToArray()
End Function

Вот новая попытка, которую я попробовал. Я все еще не могу заставить ее работать 

    Public Function SortLexicoGraphicallyBigIntegerArray(ByRef data As Byte()) As UInteger()
        Dim OrderedRotations As New List(Of UInteger)
        Dim index As Integer = 0
        Dim data1 As Byte()
        Dim data2 As Byte()

        Dim rotation As UInteger = 0
        Dim eachRotation As Integer = 0
        Dim TryAgain As Boolean = False

        For rotation = 0 To data.Length - 1
            data1 = GetRotation(data, rotation)
            OrderedRotations.Add(rotation)
            If OrderedRotations.Count > 1 Then
redo:
                data1 = GetRotation(data, OrderedRotations(rotation))
                For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                    If OrderedRotations(eachRotation) = OrderedRotations(rotation) Then Continue For
                    data2 = GetRotation(data, OrderedRotations(eachRotation))

                    For index = 0 To data.Length - 1
                        If data1(index) = data2(index) Then
                            Continue For
                        ElseIf data1(index) < data2(index) Then
                            Exit For
                        ElseIf data1(index) > data2(index) Then
                            Dim tmpFirst As UInteger = OrderedRotations(rotation)
                            OrderedRotations(rotation) = OrderedRotations(eachRotation)
                            OrderedRotations(eachRotation) = tmpFirst
                            GoTo redo
                            Exit For
                        End If
                    Next
                Next
            End If
        Next

        Return OrderedRotations.ToArray()
    End Function

Что-то связанное с многослойными сравнениями, которые я могуне понял.

1 Ответ

0 голосов
/ 07 декабря 2018

Вы можете сделать общий алгоритм двоичной сортировки: - 

Dim flag As Boolean
Dim tempvalue As dataarraytype
Dim i As Integer

Do
    flag = False
    For i = 0 to dataarray.length - 2
        If dataarray(i) > dataarray(i+1) Then   'Do the test you require
            'Swap values
            tempvalue = dataarray(i)
            dataarray(i) = dataarray(i+1)
            dataarray(i+1) = tempvalue
            flag = True
        End If
    Next
Loop While flag

Решено с помощью ответа FateOfLeap, вот полный рабочий код 

Public Function SortLexicoGraphicallyBigIntegerArray(ByRef data As Byte()) As UInteger()
    Dim OrderedRotations As New List(Of UInteger)
    Dim index As Integer = 0
    Dim data1 As Byte()
    Dim data2 As Byte()

    Dim rotation As UInteger = 0
    Dim eachRotation As Integer = 0
    Dim TryAgain As Boolean = False

    For rotation = 0 To data.Length - 1
        data1 = GetRotation(data, rotation)
        OrderedRotations.Add(rotation)
        If OrderedRotations.Count > 1 Then
            Dim flag As Boolean
            Do
                flag = False

                For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                    data1 = GetRotation(data, OrderedRotations(rotation))
                    If OrderedRotations(eachRotation) = OrderedRotations(rotation) Then Continue For
                    data2 = GetRotation(data, OrderedRotations(eachRotation))

                    For index = 0 To data.Length - 1
                        If data1(index) > data2(index) Then
                            Exit For
                        ElseIf data1(index) < data2(index) Then
                            Dim tmpFirst As UInteger = OrderedRotations(rotation)
                            OrderedRotations(rotation) = OrderedRotations(eachRotation)
                            OrderedRotations(eachRotation) = tmpFirst
                            flag = True
                        End If
                    Next
                Next
            Loop While flag
        End If
    Next

    Return OrderedRotations.ToArray()
End Function
...