# Necklace Swap Problem for Rhythmic Similarity Measures

Raphael 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.

## Abstract

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).

Bibtex entry.

## Contact details

## Publication Admin