Anonymous user
Most frequent k chars distance: Difference between revisions
→{{header|Kotlin}}
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 845:
SDF(input1, input2, 2, 100) = 88
</pre>
=={{header|Nim}}==
It is impossible to get consistent results. We chose to implement Wikipedia algorithm (note that the page is no longer available, except in Internet Archive). With this algorithm, we get the same results as those of Wikipedia except for the last example where we get 91 instead of 83.
In order to avoid the limitation to 10 occurrences, we chose to use an ordered table (equivalent to Python OrderedDict). We could have used Kotlin solution or used a sequence of tuples (char, count) but the ordered table gives better performance.
<lang Nim>import algorithm, sugar, tables
type CharCounts = OrderedTable[char, int]
func `$`(counts: CharCounts): string =
for (c, count) in counts.pairs:
result.add $c & $count
func mostFreqKHashing(str: string; k: Positive): CharCounts =
var counts: CharCounts # To get the counts in apparition order.
for c in str: inc counts.mgetOrPut(c, 0)
counts.sort((x, y) => cmp(x[1], y[1]), Descending) # Note that sort is stable.
var count = 0
for c, val in counts.pairs:
inc count
result[c] = val
if count == k: break
func mostFreqKSimilarity(input1, input2: CharCounts): int =
for c, count in input1.pairs:
if c in input2:
result += count
func mostFreqKSDF(str1, str2: string; k, maxDistance: Positive): int =
maxDistance - mostFreqKSimilarity(mostFreqKHashing(str1, k), mostFreqKHashing(str2, k))
const
Pairs = [("night", "nacht"),
("my", "a"),
("research", "research"),
("aaaaabbbb", "ababababa"),
("significant", "capabilities")]
for (str1, str2) in Pairs:
echo "str1: ", str1
echo "str2: ", str2
echo "mostFreqKHashing(str1, 2) = ", mostFreqKHashing(str1, 2)
echo "mostFreqKHashing(str2, 2) = ", mostFreqKHashing(str2, 2)
echo "mostFreqKSDF(str1, str2, 2, 10) = ", mostFreqKSDF(str1, str2, 2, 10)
echo()
const
S1 = "LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLV"
S2 = "EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG"
echo "str1: ", S1
echo "str2: ", S2
echo "mostFreqKHashing(str1, 2) = ", mostFreqKHashing(S1, 2)
echo "mostFreqKHashing(str2, 2) = ", mostFreqKHashing(S2, 2)
echo "mostFreqKSDF(str1, str2, 2, 100) = ", mostFreqKSDF(S1, S2, 2, 100)</lang>
{{out}}
<pre>str1: night
str2: nacht
mostFreqKHashing(str1, 2) = n1i1
mostFreqKHashing(str2, 2) = n1a1
mostFreqKSDF(str1, str2, 2, 10) = 9
str1: my
str2: a
mostFreqKHashing(str1, 2) = m1y1
mostFreqKHashing(str2, 2) = a1
mostFreqKSDF(str1, str2, 2, 10) = 10
str1: research
str2: research
mostFreqKHashing(str1, 2) = r2e2
mostFreqKHashing(str2, 2) = r2e2
mostFreqKSDF(str1, str2, 2, 10) = 6
str1: aaaaabbbb
str2: ababababa
mostFreqKHashing(str1, 2) = a5b4
mostFreqKHashing(str2, 2) = a5b4
mostFreqKSDF(str1, str2, 2, 10) = 1
str1: significant
str2: capabilities
mostFreqKHashing(str1, 2) = i3n2
mostFreqKHashing(str2, 2) = i3a2
mostFreqKSDF(str1, str2, 2, 10) = 7
str1: LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLV
str2: EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG
mostFreqKHashing(str1, 2) = L9T8
mostFreqKHashing(str2, 2) = F9L8
mostFreqKSDF(str1, str2, 2, 100) = 91</pre>
=={{header|Perl}}==
| |||