First, a few vague definitions:
Circular queues (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle"). wikipedia
Let's say that 2 circular queues are equal if they have the exact same elements in them and the order of items in them are exactly the same.
Example: if we form a circular queue from the string "absa" and one from "bsaa", the two will be equivalent.
My task is to group together "cyclic equivalent" strings. I'm trying to find a "base representation" for all "cyclic equivalent" strings to use it as an "index" in a hash table which would make grouping them more efficient.
Help me find an algorithm that can assign a single unique representation to all equal circular queues!
- is it even possible? (let alone useful?)
- what about problematic ones like "asdasd"? (see balanced bike wheel analogy)
Some ideas to base the algorithm on:
- bicycle wheel analogy: Imagine your bike's wheels have colored spokes, all kinds of colors, each color having a different weight (terrible idea for everyone except for computer scientists). If you flip your bike upside down letting the wheel spin freely, the part of the wheel with the most torque will rotate to the bottom and the wheel will stay in that "base position" and that bottom point of the wheel could be called its "base index". If we recorded the order of the colored spokes starting at that point, that order could be called a linear "base representation" of the wheel. This would not happen in the case of a properly balanced wheel, which would not start rotating. What could we do in that case?
Some practical use cases:
- finding equivalent circular transportation routes on a map (like those of public transportation) regardless of starting and ending point