New answers tagged

0

This is a nearest-neighbor problem, and there are a variety of algorithms for the problem. The simplest is a k-d tree, and there are more sophisticated data structures as well. Another approach is to use locality-sensitive hashing. However, the effectiveness of these methods depends heavily on the dimension (i.e., on the length of the strings). Practical ...


0

We need to find the minimum number of transpositions that take one string $a$ to another string $b$, where $a, b$ are permutations. It looks like you are looking for the minimum distance between two given vertices $a, b \in S_n$ in the complete transposition graph, which is the Cayley graph of $S_n$ generated by the set of all transpositions.


Top 50 recent answers are included