Minimize sequence with rules
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: Minimize sequence with rules

Hybrid View

  1. #1
    Join Date
    Sep 2012
    Posts
    5

    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.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Minimize sequence with rules

    Quote Originally Posted by cuber64 View Post
    Say we have a sequence 1 1 2 4 4 3 3 2
    I may be missing something but finding the "minimal" sequence seems trivial. It's just to order the items. With your example it would be,

    1 1 2 2 3 3 4 4

  3. #3
    Join Date
    Jan 2009
    Posts
    596

    Re: Minimize sequence with rules

    Quote Originally Posted by nuzzle View Post
    I may be missing something but finding the "minimal" sequence seems trivial. It's just to order the items. With your example it would be,

    1 1 2 2 3 3 4 4
    What cuber64 actually means is that he/she wants an algorithm to find the canonical form for a given sequence, under the equivalence relation whereby permutations and circular re-orderings are equivalent.

    @cuber64: I think the best you could get for this is O(n), as any algorithm will likely have to look at all the letters of the sequence to determine the canonical form. Or at least all except the last one or two letters, as these can be determined by what is left over after looking at the rest.

    Not much help, I know, but sometimes having a bound on what you can likely achieve will help you know when to stop looking for a better approach

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Minimize sequence with rules

    Quote Originally Posted by Peter_B View Post
    What cuber64 actually means is that he/she wants an algorithm to find the canonical form for a given sequence, under the equivalence relation whereby permutations and circular re-orderings are equivalent.
    To me it looks like he's defined the "canonical form" to be the ordered sequence. It can be reached for any sequence by sorting it. It involves a series of permutations and can be achieved in O(N*lnN) time.

  5. #5
    Join Date
    Sep 2012
    Posts
    5

    Re: Minimize sequence with rules

    No, it's what Peter_B said. I want to find a cannonical form of a given sequence, which is not just sorting it.

    e.g. 1212 != 1122

    Anyways, I would be satisfied in any canonical form that would be quick to find, not necessarily the minimal in the sense that it is bigger in the sence of integers, 1212 > 1122.

    For the meanwhile, I'll just use the O(n^2) approach, since I can't find a better approach.

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: Minimize sequence with rules

    Quote Originally Posted by cuber64 View Post
    I want to find a cannonical form of a given sequence, which is not just sorting it.
    Well, what is it then?

    Or rather how do you define it in this case?

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center