0
$\begingroup$

An equivalence relation on binary strings calls two strings equivalent if one can be obtained from the other by a cyclic permutation of the characters. Combinatorialists call the equivalence classes of such strings "necklaces".

Given two binary strings of length $n$, the brute-force method for determining if they are equivalent is just iteratively cycling one of them $n$ times and comparing to see if the other string is ever obtained. Is there a faster algorithm? Perhaps there is a list of invariants that are fast to compute and uniquely determine the necklace? Or perhaps through a bijection with some other set, like the irreducible polynomials over $\mathbb{F}_2$ with degree dividing $n$, it is possible to more efficiently solve the problem and transfer back?

A related question: is there an algorithm better than iterative cycling and comparison to get a computer to recognize if a string is periodic? That is, is there a fast algorithm to compute the stabilizer subgroup of a string under the action of the cyclic group of order $n$?

$\endgroup$
1
$\begingroup$

If you really wanted to you could get worst-case $O(n\log n)$ using a fast fourier transform, at least when $n$ is a power of $2$.

I know nothing about such things, but I doubt that this could be worth the trouble, because it seems to me that the brute-force approach is going to be $O(n)$ on average. Because you can compare two random strings of arbitrary length in constant average time:

The probability you get a "no" after looking at the first character is $1/2$. The probability that you have to look at the first and then the second characters to get a "no" is $1/4$. And so on; the expected value of the number of character comparisons needed is no larger than $$\sum_{k=1}^\infty k 2^{-k}<\infty.$$

$\endgroup$
  • $\begingroup$ This right when you look at an individual comparison. If you have lots of necklaces and want to compare them pairwise, it may pay off to perform $O(n)$ or $O(n\log n)$ precomputation operations per necklace and then only require $O(1)$ operations per comparison. The FFT might be a good candidate here, since it combines complete information with good differentiation already for a single comparison. It would also immediately tell you whether a sequence is periodic. $\endgroup$ – joriki Jun 24 '16 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.