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)

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

  • Cite this