Re: [math-fun] Scrambled necklaces
A few possibly dumb questions: 1. Does the circular character string have marked "ends", or merely a circular ordering? 2. Is it assigned a direction (orientation)? 3. It seems that the reversals are performed consecutively. Does it matter what order they're performed in? If so, what order should they be performed in? —Dan Keith Lynch wrote: ----- What, if anything, is known about the following process? Take a circular character string, i.e. the end is attached to the beginning (a "necklace"). For each instance of each character in it, in lexical order, reverse all characters between successive instances of that character. For instance: reverse [e] revesre [r] rsevere [s] esrerev [v] erersev Here's an example using *this* sentence: isexample'sinte anceng ere:Hen s* us *th Questions include: * For each size of necklace, what's the most such processes it could take to return to the original state? And how large an alphabet would that require? For instance "reverse" takes 14 steps: reverse erersev rsereve severer everser rerseve serever everers versere ersever erevers vererse erserev rsevere reverse For my sentence example above, 16320 steps are required to return to the original sentence. * Can you ever get a reverse of the original string? * Can you ever get a rotation of the original string? * What invariants are there, other than the obvious one that the quantities of each character are unchanged? * If someone were to alternate several times between this process and exclusive-oring the text with as many repeats of a secret string as it takes to cover the text, is there any way to decrypt the result that's faster than trying all possible secret strings up to the length of the actual secret string? -----
14 is divisible by 7 and 16320 is divisible by 40. Could it be that the size of each orbit is always divisible by the length of the string? Jim On Fri, Sep 25, 2020 at 12:31 AM Dan Asimov <dasimov@earthlink.net> wrote:
A few possibly dumb questions:
1. Does the circular character string have marked "ends", or merely a circular ordering?
2. Is it assigned a direction (orientation)?
3. It seems that the reversals are performed consecutively. Does it matter what order they're performed in? If so, what order should they be performed in?
—Dan
Keith Lynch wrote: ----- What, if anything, is known about the following process?
Take a circular character string, i.e. the end is attached to the beginning (a "necklace"). For each instance of each character in it, in lexical order, reverse all characters between successive instances of that character.
For instance: reverse [e] revesre [r] rsevere [s] esrerev [v] erersev
Here's an example using *this* sentence: isexample'sinte anceng ere:Hen s* us *th
Questions include:
* For each size of necklace, what's the most such processes it could take to return to the original state? And how large an alphabet would that require? For instance "reverse" takes 14 steps:
reverse erersev rsereve severer everser rerseve serever everers versere ersever erevers vererse erserev rsevere reverse
For my sentence example above, 16320 steps are required to return to the original sentence.
* Can you ever get a reverse of the original string?
* Can you ever get a rotation of the original string?
* What invariants are there, other than the obvious one that the quantities of each character are unchanged?
* If someone were to alternate several times between this process and exclusive-oring the text with as many repeats of a secret string as it takes to cover the text, is there any way to decrypt the result that's faster than trying all possible secret strings up to the length of the actual secret string? -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Dan Asimov -
James Propp