0

I have a circular data structure that has a reading direction and a starting point. (Internally it could be a directed graph, linked list or just an array that gets rotated using modulo.) I want to have a way to normalize the starting point of the data structure in a way that the same data input yields the same starting point.

A = [1,2,3]
B = [2,3,1]
C = [3,1,2]
assert(Normalized(A) == Normalized(B))
assert(Normalized(B) == Normalized(C))

I don't care so much about a specific rotation. (Just, of corse, the circular order and direction needs to be persisted :P )

Here is a cool answer about comparing circular structures: Interview question: Check if one string is a rotation of other string

[EDIT: Removed non-working approach]

I feel, that smart people thought about this before. What is the terminology I am missing or what are known algorithms for normalizing the rotation of circular data structures?

AyJayKay
  • 103
  • 6

1 Answers1

1

what are known algorithms for normalizing the rotation of circular data structures?

The goal is a rotation, so that the same circle input ends up on the same rotation. One way is to simply look for the group that describes the biggest number, if you look at the whole group. (The rotation with the greatest number(s) first)

[1,2,3] -> [3,1,2]
[2,3,1] -> [3,1,2]

(Needless to say, this works with the smallest group, as well.)

What is the terminology I am missing

https://en.wikipedia.org/wiki/Circular_buffer

https://en.wikipedia.org/wiki/Modular_arithmetic

AyJayKay
  • 103
  • 6