105 lines
3 KiB
Text
105 lines
3 KiB
Text
' 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
|