Results 1 to 4 of 4

Thread: [RESOLVED] How to order array in lexicographical order vb.net

Hybrid View

  1. #1

    Thread Starter
    Lively Member
    Join Date
    Apr 2009
    Posts
    73

    Resolved [RESOLVED] How to order array in lexicographical order vb.net

    This is kinda complicated for me to understand because the arrays are created in runtime I cannot create all the arrays right away as they exceed the memory limits (40 GB+) I want to be able to sort them all on the fly.

    Code:
            Dim test() As Byte = New Byte() {50, 40, 30, 10, 10}
            Dim answer() As UInteger = SortLexicoGraphicallyBigIntegerArray(test)
    The answer is the each Rotation sorted from lowest array value to highest array value.

    Code:
        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
    When I sort this array above by hand I should get

    Code:
        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
    So the answer should be
    Code:
    2, 1, 3, 4, 0

    I get stuck in a infinite loop and I can't put my finger on it

    Here is my Code

    Code:
        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
    Here is a new attempt I tried it still gets the infinite loop and doesn't function well.. I can't grasp the concept

    Code:
        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
    Last edited by pkedpker; Dec 6th, 2018 at 06:24 PM.

  2. #2
    PowerPoster ChrisE's Avatar
    Join Date
    Jun 2017
    Location
    Frankfurt
    Posts
    2,828

    Re: How to order array in lexicographical order vb.net

    Hi,
    try sorting with a DataTable

    here a sample with 6 Columns, you can choose by which column you want to sort

    Code:
    Public Class Form1
    
        Private mRandomClass As New Random()
    
        Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
            Dim dtb As New System.Data.DataTable
            dtb.Columns.Add("Column1", GetType(Integer))
            dtb.Columns.Add("Column2", GetType(Integer))
            dtb.Columns.Add("Column3", GetType(Integer))
            dtb.Columns.Add("Column4", GetType(Integer))
            dtb.Columns.Add("Column5", GetType(Integer))
            dtb.Columns.Add("Column6", GetType(Integer))
    
            'Add rows
            For i As Integer = 1 To 1000
                dtb.LoadDataRow(New Object() {2 + i, _
                                           mRandomClass.Next, _
                                           mRandomClass.Next, _
                                           mRandomClass.Next, _
                                           mRandomClass.Next, _
                                           mRandomClass.Next}, _
                                       True)
            Next
            Dim dvw As DataView = dtb.DefaultView
            dvw.Sort = "Column2 ASC"
            Dim dtbSorted As DataTable = dvw.ToTable()
            DataGridView1.DataSource = dtbSorted
    
        End Sub
    
    End Class
    HTH
    to hunt a species to extinction is not logical !
    since 2010 the number of Tigers are rising again in 2016 - 3900 were counted. with Baby Callas it's 3901, my wife and I had 2-3 months the privilege of raising a Baby Tiger.

  3. #3
    Lively Member
    Join Date
    Jan 2013
    Posts
    124

    Re: How to order array in lexicographical order vb.net

    Hi pkedpker,
    If I understood what you want to do, here's a working method to do it:

    Code:
            'Fill the arrays 
            Dim R0() As Byte = New Byte() {50, 40, 30, 10, 10}
            Dim R1() As Byte = New Byte() {10, 50, 40, 30, 10}
            Dim R2() As Byte = New Byte() {10, 10, 50, 40, 30}
            Dim R3() As Byte = New Byte() {30, 10, 10, 50, 40}
            Dim R4() As Byte = New Byte() {40, 30, 10, 10, 50}
    
            'Keep an index of every array
            Dim R(2, 5) As Double
            R(0, 0) = 0
            R(0, 1) = 1
            R(0, 2) = 2
            R(0, 3) = 3
            R(0, 4) = 4
    
            'Convert every array items to one double
            R(1, 0) = CDbl(R0(0) & R0(1) & R0(2) & R0(3) & R0(4))
            R(1, 1) = CDbl(R1(0) & R1(1) & R1(2) & R1(3) & R1(4))
            R(1, 2) = CDbl(R2(0) & R2(1) & R2(2) & R2(3) & R2(4))
            R(1, 3) = CDbl(R3(0) & R3(1) & R3(2) & R3(3) & R3(4))
            R(1, 4) = CDbl(R4(0) & R4(1) & R4(2) & R4(3) & R4(4))
    
            'Show the index before sorting
            MessageBox.Show("Before order: " & R(0, 0) & "," & R(0, 1) & "," & R(0, 2) & "," & R(0, 3) & "," & R(0, 4))
    
            'Do sort the double and the index
            Dim x, y As Double
            For i = 0 To 4
                For j = 0 To 4
                    If R(1, i) < R(1, j) Then
                        x = R(1, j)
                        R(1, j) = R(1, i)
                        R(1, i) = x
                        y = R(0, j)
                        R(0, j) = R(0, i)
                        R(0, i) = y
                    End If
                Next
            Next
    
            'Show the index after sorting
            MessageBox.Show("After order: " & R(0, 0) & "," & R(0, 1) & "," & R(0, 2) & "," & R(0, 3) & "," & R(0, 4))
    Hope that helps

  4. #4

    Thread Starter
    Lively Member
    Join Date
    Apr 2009
    Posts
    73

    Re: How to order array in lexicographical order vb.net

    Solved it
    One guy suggested this

    You can do a general binary sort algorithm:-

    Code:
    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
    I adapted it and here is my working code

    Code:
    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
    Last edited by pkedpker; Dec 6th, 2018 at 07:46 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width