Aligning overlap of ordered and unordered lists

I'm looking for an algorithm that can find/assign order and overlap given a list of ordered elements and a list of unordered elements. (of which overlap might or might not exist).

For this example I'll use the integers but they could just as well be peoples names, ID codes etc. IE the number can't be used to solve the real problem but to help explain the problem I used the ordered set (1,2,3,4,5,6,7,8,9,10) as the holy grail answer.

Input:

Ordered List of Lists: (1,2,3,4), (8,9,10), (3,4,5)

UnOrdered List of Lists: (3,4,2), (6,4,5,7), (10,9)

Thought process in how I do this algorithm in my head:

1. list 3,4,5 and 1,2,3,4 are ordered and have 3,4 in common therefore the 2 ordered lists overlap to form: 1,2,3,4,5 in that order.
2. The unordered list 3,4,2 is a subset of ordered list 1,2,3,4,5 therefor it could be reordered as 2,3,4 and said to overlap the ordered list 1,2,3,4,5
3. Same idea (as step 2) for the ordered list 8,9,10 when compared with the unordered 10,9. It should be 9,10 overlapped with 8,9,10.
4. Now comparing ordered list 1,2,3,4,5 and the unordered 6,4,5,7 they have an intersection set of 4,5 so you could conclude that its 1,2,3,4,5,(6,7|7,6) where (6,7|7,6) means that its either a 6 followed by a 7 or a 7 followed by a 6 (but its unknown which is correct)

Output:

• I would like to beable to parse a matrix/tree/whatever kind of data structure to see what overlapped where and in what order
• and a summarized list containing sets of partially known order
  • set1: 1,2,3,4,5,(6,7|7,6)
  • set2: 2: 8,9,10

Does anyone know of a similar problem or algorithm I could use? Ideally it would be i开发者_开发技巧n Perl but pseudo code or algorithms from another language would be fine.

Thanks

If I understand this right, you need one ordered list from a set of ordered and unordered lists. A possible solution would be to iterate over all the values in all the sets and add them to a hash table structure. In implementation terms that could be a c++ map, java hashmap, python dictionary etc. That would look like:

for i over all sets S //(Ordered and Unordered)

  for j over all values in S[i]

      H.insert(S[i][j]) //H is the hash table

Now iterate over the hash table entries to get the required ordered list. This is quite practical and optimal.

A not-so-practical-solution but worth mentioning for its niceness is this:

1. Assign every unique number a corresponding prime number. For example, in your example case, map the numbers as follows: p[1] = 2, p[2]=3, p[3]=5, p[4]=7, p[5]=11, p[6]= 13, p[7]=17, p[8]=19, p[9]=23, p[10]=29;

2. Now, each set Si can be represented by a value Vi- the product of the corresponding primes. So a set Si=(1,2,3) (or for that matter (2,1,3)) would have value Vi=p[1]*p[2]*p[3]

3. Find the LCM of all the Vi 's. Call this V. V=For all i LCM{Vi}

4. Factorise V into its prime factors. Each prime number represents an element in your final ordered list.

This second solution is neat but breaks down for practical purposes because we enter bignum space very quickly.

Hope at least one of these work for you!