Necklace Swap Problem for Rhythmic Similarity MeasuresRaphael Clifford, 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).