VB.NET 以最少的步骤自定义复杂排序

Question

我还想说，我不关心算法生成哪个解，因为我知道对于相同的步数有很多解。

我只想要任何对当前拼图来说可能移动最少的解决方案。

谢谢。我真的没有任何模式可以想到，我所知道的是最小的数字必须放在前面，最大的数字必须放在后面，但诀窍是它一次移动 2 个数字，一个从前面，一个从后面一起移动，就像使用更可修改的堆栈一起排序。

这个游戏只包含 2 个 Action ..

• 在任何偏移处向左循环旋转(最后一个字节除外)向右
• 任何偏移量的循环旋转(最后一个字节除外)

这是函数代码

Public Function CyclicRotationOffset(ByVal data() As Byte, ByVal beginOffset As Integer, ByVal leftDirection As Boolean) As Byte()

    'Left Direction = true
    '--------------------------------------------------------
    'Shifted cyclically rotation If [a, b, c] then [b, c, a]
    '--------------------------------------------------------
    'Left Direction = false
    '--------------------------------------------------------
    'Shifted cyclically rotation If [a, b, c] then [c, a, b]
    '--------------------------------------------------------

    If beginOffset = UBound(data) Then
        'last byte cannot do anything.
        Return data
    End If

    Dim newdata() As Byte
    ReDim newdata(UBound(data))

    If leftDirection = True Then
        newdata(UBound(newdata)) = data(beginOffset) '1st element will be last.
        For i = beginOffset To UBound(data) - 1
            newdata(i) = data(i + 1)
        Next i
    Else
        newdata(beginOffset) = data(UBound(data)) 'last element will be first.
        For i = beginOffset + 1 To UBound(data)
            newdata(i) = data(i - 1)
        Next i
    End If

    If beginOffset > 0 Then
        Buffer.BlockCopy(data, 0, newdata, 0, beginOffset)
    End If

    Return newdata
End Function

举两个例子
--------------------------------------------
数据，用蛮力(和函数)在 6 个 Action 中解决。
2, 7, 3, 1, 6, 4, 5, 8, 9
----------------------------------------------
蛮力强制旋转
3左3右
----------------------------------------------
1、左
2、左
0，对
6、对
3、左
5、对
--------------------------------------------
2, 3, 1, 6, 4, 5, 8, 9, 7
2, 3, 6, 4, 5, 8, 9, 7, 1
1, 2, 3, 6, 4, 5, 8, 9, 7
1, 2, 3, 6, 4, 5, 7, 8, 9
1, 2, 3, 4, 5, 7, 8, 9, 6
1, 2, 3, 4, 5, 6, 7, 8, 9 <- 最后一个产生排序的答案
----------------------------------------------

这是一个更难的例子(这个难住了我)
7 步解决(使用蛮力)
数据=
3、9、7、4、2、5、1、6、8
回答=
1、2、3、4、5、6、7、8、9

4 左，3 右
采取的行动
6、左
0，对
3、左
7、对
2、左
3、左
1、对

3, 9, 7, 4, 2, 5, 6, 8, 1
1, 3, 9, 7, 4, 2, 5, 6, 8
1, 3, 9, 4, 2, 5, 6, 8, 7
1, 3, 9, 4, 2, 5, 6, 7, 8
1, 3, 4, 2, 5, 6, 7, 8, 9
1, 3, 4, 5, 6, 7, 8, 9, 2
1、2、3、4、5、6、7、8、9

这是我的代码，它为第一个谜题找到 6 步解决方案，但是对于第二个谜题，它没有正确处理它，所以解决方案需要 14 步 而不是最佳7 个 Action 。

Public Structure OffsetMove
    Dim moveId As Byte
    Dim randomOffset As Byte
    Public Sub New(ByVal moveId As Byte, ByVal randomOffset As Byte)
        Me.moveId = moveId
        Me.randomOffset = randomOffset
    End Sub
End Structure

Public Function SortDataCyclic(ByVal data() As Byte) As List(Of OffsetMove)
    Dim answer() As Byte
    ReDim answer(UBound(data))
    Buffer.BlockCopy(data, 0, answer, 0, data.Length)
    Array.Sort(answer)
    Dim newdata() As Byte
    ReDim newdata(UBound(data))
    Buffer.BlockCopy(data, 0, newdata, 0, data.Length)

    Dim i As Long = 0
    Dim j As Long = 0
    Dim k As Long = 0
    Dim l As Long = 0
    Dim solutionCount As Integer = 0
    Dim movesTaken As New List(Of OffsetMove)
    Debug.Print("---------------------------------------------")

    Dim sortedPairs As New List(Of Byte)

    While j < 8
        If sortedPairs.Count >= 3 Then
            'Insertion right cyclic rotations go here
            While l < 9
                k = 0
                While k < 9
                    If newdata(k) > newdata(8) Then Exit While
                    k += 1
                End While
                If k = 9 Then
                    'fully sorted already, nothing left to insert.
                    Exit While
                End If
                newdata = CyclicRotationOffset(newdata, k, False)
                movesTaken.Add(New OffsetMove(1, k))
                printDebug(newdata)

                l += 1
            End While

            'Exit the while, everything is sorted.
            Exit While
            '1, 2, x, x, x, x
        ElseIf j + 1 < 9 AndAlso _
            newdata(j + 1) = (newdata(j) + 1) Then
            sortedPairs.Add(j)
            j += 2
            '1, x, 2, x, x, x
        ElseIf j + 2 < 9 AndAlso _
            newdata(j + 2) = (newdata(j) + 1) Then
            newdata = CyclicRotationOffset(newdata, (j + 1), True)
            movesTaken.Add(New OffsetMove(0, (j + 1)))
            printDebug(newdata)
            j = 0
            'No pair pattern at all.
        Else
            newdata = CyclicRotationOffset(newdata, j, True)
            movesTaken.Add(New OffsetMove(0, j))
            printDebug(newdata)
        End If
    End While
    Return movesTaken
End Function

Public Sub printDebug(ByVal data() As Byte)
    Debug.Print(data(0) & ", " & data(1) & ", " & data(2) & ", " & data(3) & ", " & data(4) & ", " & data(5) & ", " & data(6) & ", " & data(7) & ", " & data(8))
End Sub

Answer 1

我使用了您的代码，得到了与您不同的结果集。我认为部分原因与 while 循环中 sortedPairs.Count 的逻辑有关。我也对 I、j、k 和 l 之间的差异感到困惑。因此，我使用一些略有不同的逻辑重写了您的 While 循环。

    Dim currentNumber As Integer = 1
    Dim currentPositionOfNumber As Integer = 0

    While currentNumber - 1 < 8
        currentPositionOfNumber = GetIndexOfNumber(newdata, currentNumber)
        If currentNumber - 1 = currentPositionOfNumber Then
            'do nothing
        ElseIf currentNumber = currentPositionOfNumber Then
            'If the number needed to move is in the spot to the immediate right of where it needs to be, then just rotate left once
            newdata = CyclicRotationOffset(newdata, currentNumber - 1, True)
            movesTaken.Add(New OffsetMove(1, k))
            printDebug(newdata)
        ElseIf currentPositionOfNumber = 8 Then
            'if number needed to move is in last position, then rotate it to correct position
            newdata = CyclicRotationOffset(newdata, currentNumber - 1, False)
            movesTaken.Add(New OffsetMove(1, k))
            printDebug(newdata)
        ElseIf currentNumber = newdata(currentPositionOfNumber + 1) - 1 Then
            'if the number is not in any of the above positions, but the number immediately to it's right is the next higher, then just rotate left until the pair are in correct position
            Do Until GetIndexOfNumber(newdata, currentNumber) = currentNumber - 1
                newdata = CyclicRotationOffset(newdata, currentNumber - 1, True)
                movesTaken.Add(New OffsetMove(1, k))
                printDebug(newdata)
            Loop
        Else
            'rotate left once, then rotate right to correct position
            newdata = CyclicRotationOffset(newdata, currentPositionOfNumber, True)
            movesTaken.Add(New OffsetMove(1, k))
            printDebug(newdata)
            newdata = CyclicRotationOffset(newdata, currentNumber - 1, False)
            movesTaken.Add(New OffsetMove(1, k))
            printDebug(newdata)
        End If
        currentNumber += 1
    End While

我还有一个函数可以找到正在评估的 currentNumber 在数组中的位置

Public Function GetIndexOfNumber(data() As Byte, number As Integer) As Integer
    For i = 0 To 8
        If data(i) = number Then Return i
    Next
End Function

有了这个，我得到了以下结果......测试 1 = 6 步测试 2 = 7 步