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 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
