[algogeeks] Re: Merging sequences?
Hi you problem is not very clear. But as far as i get it, it is somewhat like topological search. jus see what toplogical search is and chk if tht is wat u want. if not plz give a clearer picture of the prob. all the best bbye On 5/30/07, Edward [EMAIL PROTECTED] wrote: I'm afraid I don't really know the correct teminology do describe this problem, so I'm having trouble looking for generalised solutions. I have a set of sequences of points I must traverse in order and and I want to combine the set into one long sequence possibly with some points repeated so that it still satisfies the original sequences. So 1) A - B - C - D 2) A - C - B - D 3) B - C - A - D combined together could create a sequence of A - C - B - C - A - D 1 1 11 2 2 22 3 3 3 3 Can anyone advise me what this problem is called, or give me pointers as to a solution? I expect its a part of graph theory or something, but without knowing the right terms its hard to look it up. -- Chandrasekhar Final Year CSE NIT Allahabad --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Merging sequences?
I'm not sure what a topological search is, I understand a topological sort. AFAIK a topological sort is not a solution to my problem since it does not work if there are cycles. I'm not sure how I can be clearer with the problem, I can give another example. Given one sequence where a) V - W - X - Y - Z (V comes before W which comes before X etc) and another where b) W - Y - Z - X - V (W comes before Y which comes before Z etc) and c) T - U - W- Z - X (T comes before U which comes before W etc) an ordering of the points which supports all the sequences would be a b c T / U / V / W / / / X / Y / / Z / / / X / / V / where points V and X occur twice in the sequence because V occurs before Z in sequence 'a' and after Z in sequence 'b' and X occurs before Z in sequence 'a' and after Z in sequence 'c'. I'd like to be able to extend that to arbitrary lengths and numbers of sequences, minimizing the number of repeated points and keeping the original sequences together as much as possible. for example V T U W X Y Z X V is another ordering which satisfies the all original sequences, but T U V W X Y Z X V is better because it keeps all the points in sequence 'a' together. Hope that helps. On May 30, 1:21 pm, Chandrasekhar [EMAIL PROTECTED] wrote: Hi you problem is not very clear. But as far as i get it, it is somewhat like topological search. jus see what toplogical search is and chk if tht is wat u want. if not plz give a clearer picture of the prob. all the best bbye On 5/30/07, Edward [EMAIL PROTECTED] wrote: I'm afraid I don't really know the correct teminology do describe this problem, so I'm having trouble looking for generalised solutions. I have a set of sequences of points I must traverse in order and and I want to combine the set into one long sequence possibly with some points repeated so that it still satisfies the original sequences. So 1) A - B - C - D 2) A - C - B - D 3) B - C - A - D combined together could create a sequence of A - C - B - C - A - D 1 1 11 2 2 22 3 3 3 3 Can anyone advise me what this problem is called, or give me pointers as to a solution? I expect its a part of graph theory or something, but without knowing the right terms its hard to look it up. -- Chandrasekhar Final Year CSE NIT Allahabad- Hide quoted text - - Show quoted text - --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Merging sequences?
Ok... here is the rough idea. Since the two X's in two different sequences are treated as different X's, i guess you subscript it with the sequence no as in Xa and Xb etc. This needs to be done only with nodes that occur in a cycle. That cycle can be removed if we consider the two Xs as different Xs. I am not pretty sure as to how to difficult the coding part will be, the algo seems to be this 1) Arrange the nodes as a graph. 2) Detect cycle. 3) Remove cycle by naming one node of the cycle with the subscript. 4) Apply topological sort. 5) Finally ignore the subscript. I am not sure how to keep nodes of a sequence together. Will try to think about it. Comment on the above. Let me know if i am wrong somewhere. cheers On 5/30/07, Chandrasekhar [EMAIL PROTECTED] wrote: i am sry... i meant topological sort n not search. and i think tht shud be the solution to ur problem. i will try n post the solution asap. bbye On 5/30/07, Edward [EMAIL PROTECTED] wrote: I'm not sure what a topological search is, I understand a topological sort. AFAIK a topological sort is not a solution to my problem since it does not work if there are cycles. I'm not sure how I can be clearer with the problem, I can give another example. Given one sequence where a) V - W - X - Y - Z (V comes before W which comes before X etc) and another where b) W - Y - Z - X - V (W comes before Y which comes before Z etc) and c) T - U - W- Z - X (T comes before U which comes before W etc) an ordering of the points which supports all the sequences would be a b c T / U / V / W / / / X / Y / / Z / / / X / / V / where points V and X occur twice in the sequence because V occurs before Z in sequence 'a' and after Z in sequence 'b' and X occurs before Z in sequence 'a' and after Z in sequence 'c'. I'd like to be able to extend that to arbitrary lengths and numbers of sequences, minimizing the number of repeated points and keeping the original sequences together as much as possible. for example V T U W X Y Z X V is another ordering which satisfies the all original sequences, but T U V W X Y Z X V is better because it keeps all the points in sequence 'a' together. Hope that helps. On May 30, 1:21 pm, Chandrasekhar [EMAIL PROTECTED] wrote: Hi you problem is not very clear. But as far as i get it, it is somewhat like topological search. jus see what toplogical search is and chk if tht is wat u want. if not plz give a clearer picture of the prob. all the best bbye On 5/30/07, Edward [EMAIL PROTECTED] wrote: I'm afraid I don't really know the correct teminology do describe this problem, so I'm having trouble looking for generalised solutions. I have a set of sequences of points I must traverse in order and and I want to combine the set into one long sequence possibly with some points repeated so that it still satisfies the original sequences. So 1) A - B - C - D 2) A - C - B - D 3) B - C - A - D combined together could create a sequence of A - C - B - C - A - D 1 1 11 2 2 22 3 3 3 3 Can anyone advise me what this problem is called, or give me pointers as to a solution? I expect its a part of graph theory or something, but without knowing the right terms its hard to look it up. -- Chandrasekhar Final Year CSE NIT Allahabad- Hide quoted text - - Show quoted text - -- Chandrasekhar Final Year CSE NIT Allahabad -- Chandrasekhar Final Year CSE NIT Allahabad --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
