We have a circular sequance, where the letters 1,...n repeat twice (and letters can be permuted). I am trying to find a efficient algorithm to return the minimal representation of a sequence.

Example:
Say we have a sequence 1 1 2 4 4 3 3 2
I dont distinguish this sequence with the sequence 4 4 3 3 2 1 1 2 (circularity, i cut the first one before 4)
I also don't distinguish the first sequence with 4 4 3 1 1 2 2 3 (permutation 1 -> 4, 2 -> 3, 4 -> 1, 3 -> 2)

I would like an algorithm that converts a sequence to the minimal possible sequence of its kind (minimal when reading left to right,
for example 1 1 2 3 2 3 < 1 2 3 1 2 3, since the 2nd letter is 1 in the first seq. but 2 in the 2nd).

Of course it is possible to do it in quadratic time, since we can just loop through all starting positions and renumerate so the first occurence of a letter is 1, the second is 2, ...

Since I have millions of such sequences (all about 20 - 30 letters long) I would like a more efficient one (say running in linear or n ln(n) time).
Don't need the code, just the idea.