How to resolve the algorithm Superpermutation minimisation step by step in the FreeBASIC programming language
How to resolve the algorithm Superpermutation minimisation step by step in the FreeBASIC programming language
Table of Contents
Problem Statement
A superpermutation of N different characters is a string consisting of an arrangement of multiple copies of those N different characters in which every permutation of those characters can be found as a substring. For example, representing the characters as A..Z, using N=2 we choose to use the first two characters 'AB'. The permutations of 'AB' are the two, (i.e. two-factorial), strings: 'AB' and 'BA'. A too obvious method of generating a superpermutation is to just join all the permutations together forming 'ABBA'. A little thought will produce the shorter (in fact the shortest) superpermutation of 'ABA' - it contains 'AB' at the beginning and contains 'BA' from the middle to the end. The "too obvious" method of creation generates a string of length N!*N. Using this as a yardstick, the task is to investigate other methods of generating superpermutations of N from 1-to-7 characters, that never generate larger superpermutations. Show descriptions and comparisons of algorithms used here, and select the "Best" algorithm as being the one generating shorter superpermutations. The problem of generating the shortest superpermutation for each N might be NP complete, although the minimal strings for small values of N have been found by brute -force searches.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Superpermutation minimisation step by step in the FreeBASIC programming language
Source code in the freebasic programming language
' version 28-06-2018
' compile with: fbc -s console
Function superpermsize(n As UInteger) As UInteger
Dim As UInteger x, y, sum, fac
For x = 1 To n
fac = 1
For y = 1 To x
fac *= y
Next
sum += fac
Next
Function = sum
End Function
Function superperm(n As UInteger) As String
If n = 1 Then Return "1"
Dim As String sup_perm = "1", insert
Dim As String p, q()
Dim As UInteger a, b, i, l, x
For x = 2 To n
insert = IIf(x < 10, Str(x), Chr(x + 55))
l = Len(sup_perm)
If l > 1 Then l = Len(sup_perm) - x +2
ReDim q(l)
For i = 1 To l
p = Mid(sup_perm, i, x -1)
If x > 2 Then
For a = 0 To Len(p) -2
For b = a+1 To Len(p) -1
If p[a] = p[b] Then Continue For, For, For
Next
Next
End If
q(i) = p + insert + p
Next
sup_perm = q(1)
For i = 2 To UBound(q)
a = x -1
Do
If Right(sup_perm, a) = Left(q(i), a) Then
sup_perm += Mid(q(i), a +1)
Exit Do
End If
a -= 1
Loop
Next
Next
Function = sup_perm
End Function
' ------=< MAIN >=------
Dim As String superpermutation
Dim As UInteger n
For n = 1 To 10
superpermutation = superperm(n)
Print Using "### ######## ######## "; n; superpermsize(n); Len(superpermutation);
If n < 5 Then
Print superpermutation
Else
Print
End If
Next
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
You may also check:How to resolve the algorithm Random numbers step by step in the MiniScript programming language
You may also check:How to resolve the algorithm Memory allocation step by step in the Delphi programming language
You may also check:How to resolve the algorithm Soloway's recurring rainfall step by step in the Rust programming language
You may also check:How to resolve the algorithm Golden ratio/Convergence step by step in the Ol programming language
You may also check:How to resolve the algorithm Apply a digital filter (direct form II transposed) step by step in the Julia programming language