Necklace Swap Problem for Rhythmic Similarity Measures
, M. Mohamed, Y. Pinzon, Necklace Swap Problem for Rhythmic Similarity Measures
. Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE '05)
. ISBN 3-540-29740-5, pp. 234–245. November 2005. No electronic version available.
Given two n-bit (cyclic) binary strings, A and B,
represented on a circle (necklace instances). Let each sequence
have the same number k of 1's. We are interested in computing
the cyclic swap distance between A and B, i.e., the
minimum number of swaps needed to convert A to B, minimized
over all rotations of B. We show that this distance may be
computed in O(k^2).