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 1 1 > > > > 2 2 2 2 > > > > 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 -~----------~----~----~----~------~----~------~--~---
