Hi all, I have run into a problem where I have n number of elements and m number of stacks. Each stack consists of 0 or more elements and each element can be in 1 or more stacks. So now the problem is how do I go about merging the m stacks into 1 global stack while preserving the order of the elements described in each of the m stacks. A simple example is given below:
Elements: A, B, C, D, E Stacks: (left to right represents bottom to top) Stack 1: C | A Stack 2: B | C | E Stack 3: E | D So one possible solution is B | C | A | E | D. In this scenario there can be more than 1 solutions. (alternative solution is B | C | E | A | D ). For now, we will assume there is no cyclic issue such as the example below: (where the order between C and A cannot be determined) Stack 1: C | A Stack 2: B | A | C | E Stack 3: E | D Would appropriate if anyone can suggest a solution apart from the naive solution of at each insertion of the element e into the global stack check all the stacks which e is on and verify insertion does not violate the ordering. Since the number of elements I am looking at is in the thousands range and the number of stack is also in the thousands range. Naive method would probably take ages to complete. thuan --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
