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 F_2 with degree dividing n, it is possible to more efficiently solve the problem and transfer back?

obojeneqk 2022-09-13 Answered
Determining when two binary strings represent the same necklace or when one binary string is periodic
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 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?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Makhi Adams
Answered 2022-09-14 Author has 13 answers
Step 1
If you really wanted to you could get worst-case O(nlogn) 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:
Step 2
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
k = 1 k 2 k < .
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2020-11-01
Solve the following problems applying Polya’s Four-Step Problem-Solving strategy.
If six people greet each other at a meeting by shaking hands with one another, how many handshakes take place?
asked 2021-03-02
In how many ways can 7 graduate students be assigned to 1 triple and 2 double hotel rooms during a conference
asked 2022-09-30
How can I show that PGL(2,9) is not isomorphic to S 6 ?
My primary idea is to compare the size of conjugacy classes of two well-chosen elements in these groups. Is there another simpler approach?
asked 2021-01-30
The standard deviation of daily iron intake in the larger population of 9-to 11-year-old boys was 5.56 mg. We want to test whether the standard deviation from the low-income group is comparable to that of the general population
asked 2022-09-06
Determine hollow marble with least number of weighings
We have 135 boxes each containing 100 marbles which look identical and weigh 10 grams, with the exception of one box, which contains hollow marbles of 9 grams each. By using a scale that can weight up to 999 grams, what is the least number of weightings required to determine the box with the hollow marbles?
Well, I know the method of numbering the boxes and then taking 1 marble from box 1, 2 from box 2 etc and then compare the result with k = 1 135 k 10, but this is 91800, so we would roughly need 100 weighings! Maybe we can split the 135 boxes into two groups, 68 + 67, then from the first group weigh one of each, to see if the scale displays 680 or 679, then continue with either group which contains the hollow marble and do the same?
2nd weighing: 34 or 33
3rd: 17 or 17
And then we can apply the 1 + 2 + 3… method to determine in which of the two groups 9 or 8 are the hollow marbles.
But this way we will need 5 weighings, which I doubt is the optimum method.
asked 2022-09-14
So i have two limits that i want to solve, so i will put them together in one question, while both are probably solved with help of L'Hospital's rule. I am not sure for the second one. 1)
lim x 0 ( e 4 ( 1 x 2 ) 1 x 2 ( 1 2 x ) 1 x ) 1 x
I am having problems with this one to make it into one that can be used for L'Hospital's rule, but i cannot get it into 0 0 , there are others options as well, but i am stuck.
2) lim n ( arcsin ( 1 n ) + arcsin ( 2 n ) + . . . + arcsin ( n n ) n )
So i thought i could solve this one even if i used comparing test, but i cannot fins a way, but this one is probably not solved with L'Hospital rule, because of n, but i put it in one question, because i found both limits in the same group. I apologize for putting them in the same question if they differ too much. Any help would be appreciated.
asked 2021-10-12
a) Explain whether it is possible to use inferential methods for independent samples.
b) Explain whether there is enough information to compare the proportions using dependent samples or not.

New questions