algorithm - Restore the original order based on many incomplete ordered sets -

let's original data

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 

it got corrupted , have few incomplete sets order valid not elements present.

1, 4, 6, 7, 8, 11, 12 1, 2, 4, 5, 6, 9, 10, 12 2, 4, 7, 9, 10, 11 4, 7, 9, 12 

etc.

i have list of original elements without order.

i need restore original data possible. have no guarantee have enough information restore everything. need make sense of have , figure out parts reliable.

there may complications (but i'd solve problem without them first):

order of incomplete sets valid may have few mistakes here , there, it's written humans.

i may have additional information every pair of elements in incomplete sets like

• "there nothing between 5 , 6",
• "there else between 7 , 12 i'm not sure how many , exactly",
• "there may or may not between 3 , 4",
• "there 1 unknown item between 7 , 9"

i'd incorporate information algorithm restore more data.

my best idea far:

use incomplete arrays in sorting function this: conclude > b if there exists incomplete set in b precedes a. if there no set in both , b present return == b.

what don't have no idea parts restored , random. kind of i'm going shuffle original list of elements, sort again , see elements change place , don't. , few thousand times (the number of elements in list < 50 can use bulldozerish methods on problem)

any better suggestions?

build directed graph incomplete sets , make topological sort

some errors might found cycles (there no cycles in directed acyclic graph)