Necklace Swap Problem for Rhythmic Similarity Measures

R Clifford, M Mohamed, Y Pinzon

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)


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).
Translated title of the contributionNecklace Swap Problem for Rhythmic Similarity Measures
Original languageEnglish
Title of host publicationUnknown
PublisherSpringer Verlag
Pages234 - 245
Number of pages11
ISBN (Print)3540297405
Publication statusPublished - Nov 2005

Bibliographical note

Conference Proceedings/Title of Journal: Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE '05)


Dive into the research topics of 'Necklace Swap Problem for Rhythmic Similarity Measures'. Together they form a unique fingerprint.

Cite this