' Reverses the first k elements of a string
Function flipString(s As String, k As Integer) As String
    Dim As String res = ""
    For i As Integer = k To 1 Step -1
        res &= Mid(s, i, 1)
    Next
    res &= Mid(s, k + 1)
    Return res
End Function

' Calculate the lexicographic rank of a permutation
Function permutationRank(s As String, n As Integer, fact() As Integer) As Integer
    Dim As Integer rank = 0
    For i As Integer = 0 To n - 2
        Dim As Integer cnt = 0
        For j As Integer = i + 1 To n - 1
            If Mid(s, j + 1, 1) < Mid(s, i + 1, 1) Then cnt += 1
        Next
        rank += cnt * fact(n - i - 1)
    Next
    Return rank
End Function

' Calculate the maximum number of flips for n elements
Sub pancakeNumber(n As Integer)
    Dim As Integer i
    ' Pre-calculate factorials
    Dim As Integer fact(0 To n)
    fact(0) = 1
    For i = 1 To n: fact(i) = fact(i - 1) * i: Next

    Dim As Integer totalStates = fact(n)
    Dim As Boolean visited(0 To totalStates - 1)
    Dim As Integer dist(0 To totalStates - 1)
    Dim As String permString(0 To totalStates - 1)

    ' Initial state: ordered permutation
    Dim As String start = ""
    For i = 1 To n: start &= Str(i): Next

    Dim As Integer startRank = permutationRank(start, n, fact())
    visited(startRank) = True
    dist(startRank) = 0
    permString(startRank) = start

    Dim As String queue(0 To totalStates - 1)
    Dim As Integer head = 0, tail = 0
    queue(tail) = start
    tail += 1

    ' BFS (Breadth-First Search) to determine the maximum distance from any permutation to the ordinate
    While head < tail
        Dim As String p = queue(head)
        head += 1
        Dim As Integer currentRank = permutationRank(p, n, fact())

        ' Generar todos los flips posibles
        ' Generate all possible flips
        For i As Integer = 2 To n
            Dim As String q = flipString(p, i)
            Dim As Integer r = permutationRank(q, n, fact())

            If Not visited(r) Then
                visited(r) = True
                dist(r) = dist(currentRank) + 1
                permString(r) = q
                queue(tail) = q
                tail += 1
            End If
        Next
    Wend

    ' Find the maximum distance
    Dim As Integer maxDist = 0
    Dim As String maxPerm = ""
    For i = 0 To totalStates - 1
        If visited(i) Andalso dist(i) > maxDist Then
            maxDist = dist(i)
            maxPerm = permString(i)
        End If
    Next

    ' If no permutation was found (case n=1), use the ordinate
    If Len(maxPerm) = 0 Then
        For i = 1 To n: maxPerm &= Str(i): Next
    End If

    Print Using "Maximum number of flips to sort # elements is ##_. e.g ["; n; maxDist;
    For i = 1 To Len(maxPerm)
        If i > 1 Then Print "; ";
        Print Mid(maxPerm, i, 1);
    Next
    Print "] -> [";
    For i = 1 To n
        If i > 1 Then Print "; ";
        Print Str(i);
    Next
    Print "]"
End Sub

For n As Integer = 1 To 9
    pancakeNumber(n)
Next

Sleep