5
$\begingroup$

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
  • ?
|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ You could always choose the first representation in lexicographic order among all orders of given circular queue. $\endgroup$ – Evil Nov 5 '16 at 12:07
11
$\begingroup$

Enumerate all possible rotations of the queue. Take the lexicographically first of them. Use this as your representative. If you want a short index into a hash table, take the hash of that. Then any two equivalent queues will get the same representative / same index.

If the queue has $n$ items, implementing this naively takes $O(n^2)$ time. However, it can be done more efficiently. When the contents of the queue are random, sorting the rotations lexicographically, using a string comparison operator that only compares as much of a prefix as necessary to find the first mismatch, will have running time $O(n \log^2 n)$. If you want to get more fancy, you can do it in $O(n)$ time, using a suffix tree or suffix array; though the constant factors and implementation complexity probably won't make this worthwhile unless your queues are extremely large.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ excellent starting points, thank you! $\endgroup$ – A. Sallai Nov 5 '16 at 15:11
  • $\begingroup$ What is your $n$? $\endgroup$ – asmeurer Nov 5 '16 at 19:00
  • $\begingroup$ @asmeurer, "If the queue has $n$ items," $\endgroup$ – D.W.♦ Nov 5 '16 at 19:32
  • $\begingroup$ In that case why isn't it $O(n)$? I only see $O(n^2)$ if you're also factoring in the length of the items. $\endgroup$ – asmeurer Nov 5 '16 at 19:35
  • 1
    $\begingroup$ @asmeurer, comparing two rotations takes $O(n)$ time, in the worst case. If you want to find the minimum, you need to do at least $n-1$ comparisons. Naively, that sounds like $O(n^2)$ time. $\endgroup$ – D.W.♦ Nov 5 '16 at 20:35
4
$\begingroup$

This is a variant of the tandem repeats problem. Such a problem can be attacked via (generalized) suffix trees. This problem is strongly related to the lexicographically minimal rotation problem, for which there are fast algorithms different from the below. A more thorough description of the below appears in chapter 7 of Gusfield's "Algorithms on Strings, Trees, and Sequences".

Since every suffix of any (once through) cyclic representation of a circular queue is a prefix of any matching (once through) representation of a circular queue, construct a (generalized) suffix tree on a (twice through) cyclic representation where each character of the second copy of the string (and only those characters) are treated as terminal characters.

In your "asdasd" example, the resulting tree will have path length$^*$ three, will have three leaves, all terminal, and all of its leaves will have a pointer to the root. This is adequate evidence that your primitive cyclic string may be taken to be "asd".

Then, take the canonical string to be constructed iteratively from the root: at each node, sort the labels on the children's edges and select the edge that sorts least. Stop when you reach a (automatically terminal) leaf.

Constructing the tree for a cyclic representation of length $n$ takes $\Theta(n)$ time and space and reading out its canonicalization cannot take longer or more space. Thus, we have a $O(n)$ solution in both time and space.

$*$: Since edges may have labels of arbitrary length, the useful definition of path length in this tree is not the number of edges, but the total of the lengths of the edge labels along the path.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

Always use minimal lexicographic word to put into your hash. There is a special algorithm for that purpose called Booth's algorithm, which runs in $\mathcal O(n)$ time.

|cite|improve this answer
$\endgroup$

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.