Shortest common supersequence: Difference between revisions
Content added Content deleted
(Added FreeBASIC) |
(→{{header|FreeBASIC}}: oops! I uploaded the code from another task. Corrected.) |
||
Line 342: | Line 342: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
<syntaxhighlight lang="vbnet">Function LCS(a As String, b As String) As String |
|||
Uses 'LCS' function from [[Longest common subsequence#FreeBASIC]]: |
|||
Dim As String x, y |
|||
If Len(a) = 0 Or Len(b) = 0 Then |
|||
<syntaxhighlight lang="vbnet">Dim Shared As Double dists(0 To 9999) |
|||
Return "" |
|||
Elseif Right(a, 1) = Right(b, 1) Then |
|||
' index into lookup table of Nums |
|||
LCS = LCS(Left(a, Len(a) - 1), Left(b, Len(b) - 1)) + Right(a, 1) |
|||
Function dist(ci As Integer, cj As Integer) As Double |
|||
Else |
|||
Return dists(cj*100 + ci) |
|||
x = LCS(a, Left(b, Len(b) - 1)) |
|||
y = LCS(Left(a, Len(a) - 1), b) |
|||
If Len(x) > Len(y) Then Return x Else Return y |
|||
End If |
|||
End Function |
End Function |
||
Function SCS(u As String, v As String) As String |
|||
' energy at s, to be minimized |
|||
Dim lcsStr As String = LCS(u, v) |
|||
Function Ens(path() As Integer) As Double |
|||
Dim As |
Dim As Integer i, ui = 0, vi = 0 |
||
Dim As String sb = "" |
|||
For i = 1 To Len(lcsStr) |
|||
While ui < Len(u) Andalso Mid(u, ui + 1, 1) <> Mid(lcsStr, i, 1) |
|||
sb += Mid(u, ui + 1, 1) |
|||
ui += 1 |
|||
Wend |
|||
While vi < Len(v) Andalso Mid(v, vi + 1, 1) <> Mid(lcsStr, i, 1) |
|||
sb += Mid(v, vi + 1, 1) |
|||
vi += 1 |
|||
Wend |
|||
sb += Mid(lcsStr, i, 1) |
|||
ui += 1 |
|||
vi += 1 |
|||
Next |
Next |
||
If ui < Len(u) Then sb += Right(u, Len(u) - ui) |
|||
Return d |
|||
If vi < Len(v) Then sb += Right(v, Len(v) - vi) |
|||
Return sb |
|||
End Function |
End Function |
||
Print SCS("abcbdab", "bdcaba") |
|||
' temperature function, decreases to 0 |
|||
Print SCS("WEASELS", "WARDANCE") |
|||
Function T(k As Double, kmax As Double, kT As Double) As Double |
|||
Return (1 - k / kmax) * kT |
|||
End Function |
|||
' variation of E, from state s to state s_next |
|||
Function dE(s() As Integer, u As Integer, v As Integer) As Double |
|||
Dim As Integer su = s(u) |
|||
Dim As Integer sv = s(v) |
|||
' old |
|||
Dim As Double a = dist(s(u-1), su) |
|||
Dim As Double b = dist(s(u+1), su) |
|||
Dim As Double c = dist(s(v-1), sv) |
|||
Dim As Double d = dist(s(v+1), sv) |
|||
' new |
|||
Dim As Double na = dist(s(u-1), sv) |
|||
Dim As Double nb = dist(s(u+1), sv) |
|||
Dim As Double nc = dist(s(v-1), su) |
|||
Dim As Double nd = dist(s(v+1), su) |
|||
If v = u+1 Then Return (na + nd) - (a + d) |
|||
If u = v+1 Then Return (nc + nb) - (c + b) |
|||
Return (na + nb + nc + nd) - (a + b + c + d) |
|||
End Function |
|||
' probability to move from s to s_next |
|||
Function P(deltaE As Double, k As Double, kmax As Double, kT As Double) As Double |
|||
Return Exp(-deltaE / T(k, kmax, kT)) |
|||
End Function |
|||
' Simulated annealing |
|||
Sub sa(kmax As Double, kT As Double) |
|||
Dim As Integer s(0 To 100) |
|||
Dim As Integer temp(0 To 98) |
|||
Dim As Integer dirs(0 To 7) = {1, -1, 10, -10, 9, 11, -11, -9} |
|||
Dim As Integer i, k, u, v, cv |
|||
Dim As Double Emin |
|||
For i = 0 To 98 |
|||
temp(i) = i + 1 |
|||
Next |
|||
Randomize Timer |
|||
For i = 0 To 98 |
|||
Swap temp(i), temp(Int(Rnd * 99)) |
|||
Next |
|||
For i = 0 To 98 |
|||
s(i+1) = temp(i) |
|||
Next |
|||
Print "kT = "; kT |
|||
Print "E(s0) "; Ens(s()) |
|||
Print |
|||
Emin = Ens(s()) |
|||
For k = 0 To kmax |
|||
If k Mod (kmax/10) = 0 Then |
|||
Print Using "k: ####### T: #.#### Es: ###.####"; k; T(k, kmax, kT); Ens(s()) |
|||
End If |
|||
u = Int(Rnd * 99) + 1 |
|||
cv = s(u) + dirs(Int(Rnd * 8)) |
|||
If cv <= 0 Or cv >= 100 Then Continue For |
|||
If Abs(dist(s(u), cv)) > 5 Then Continue For |
|||
v = s(cv) |
|||
Dim As Double deltae = dE(s(), u, v) |
|||
If deltae < 0 Or P(deltae, k, kmax, kT) >= Rnd Then |
|||
Swap s(u), s(v) |
|||
Emin = Emin + deltae |
|||
End If |
|||
Next k |
|||
Print |
|||
Print "E(s_final) "; Emin |
|||
Print "Path:" |
|||
For i = 0 To Ubound(s) |
|||
If i > 0 And i Mod 10 = 0 Then Print |
|||
Print Using "####"; s(i); |
|||
Next |
|||
Print |
|||
End Sub |
|||
' distances |
|||
For i As Integer = 0 To 9999 |
|||
Dim As Integer ab = (i \ 100) |
|||
Dim As Integer cd = i Mod 100 |
|||
Dim As Integer a = (ab \ 10) |
|||
Dim As Integer b = ab Mod 10 |
|||
Dim As Integer c = (cd \ 10) |
|||
Dim As Integer d = cd Mod 10 |
|||
dists(i) = Sqr((a-c)^2 + (b-d)^2) |
|||
Next i |
|||
Dim As Double kT = 1, kmax = 1e6 |
|||
sa(kmax, kT) |
|||
Sleep</syntaxhighlight> |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre>abdcabdab |
||
WEASRDANCELS</pre> |
|||
E(s0) 510.1804163299929 |
|||
k: 0 T: 1.0000 Es: 510.1804 |
|||
k: 100000 T: 0.9000 Es: 195.1253 |
|||
k: 200000 T: 0.8000 Es: 182.4579 |
|||
k: 300000 T: 0.7000 Es: 153.4156 |
|||
k: 400000 T: 0.6000 Es: 150.7938 |
|||
k: 500000 T: 0.5000 Es: 141.6804 |
|||
k: 600000 T: 0.4000 Es: 128.4290 |
|||
k: 700000 T: 0.3000 Es: 123.2713 |
|||
k: 800000 T: 0.2000 Es: 117.4202 |
|||
k: 900000 T: 0.1000 Es: 116.0060 |
|||
k: 1000000 T: 0.0000 Es: 116.0060 |
|||
E(s_final) 116.0060090954848 |
|||
Path: |
|||
0 11 10 20 21 32 22 12 2 3 |
|||
13 14 34 33 23 24 35 25 16 15 |
|||
4 5 6 7 9 8 18 19 29 39 |
|||
49 48 38 28 27 17 26 36 47 37 |
|||
45 46 57 56 55 54 44 43 42 52 |
|||
51 41 31 30 40 50 60 61 83 73 |
|||
63 62 72 71 70 80 90 91 81 82 |
|||
92 93 94 96 97 98 99 89 79 69 |
|||
59 58 68 67 77 87 88 78 76 66 |
|||
65 75 86 95 85 84 74 64 53 1 |
|||
0 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |