
September 20th, 2012, 05:40 AM
#1
Minimize sequence with rules
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.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
