Reconstructing a sequence of numbers from separate smaller sub-sequences.

Let us consider a sequence 1,3,7,2,4,5,9,8

And we are given a set of sub-sequences as

1,3,2,4,9

1,7,4,5,9,8

There are duplicates but they appear only once in each list. The orders of the subsequences appear the same in the sub-sequences as they appear in the main sequence.

The question is can we reconstruct the original sequence from the given sub-sequences deterministically.

On the surface, we know that we can inter-leave the m elements in the n-1 gaps between the other subsequence excluding duplicates. That gives us a large number of combinations. These combinations do not indicate the unique master sequence of distinct numbers.

Moreover, the number of entries from one sequence into a gap of the second sequence is variable from one to the number of elements following the choice inclusive. The choice of elements for these gaps follows the well-known stars and bars problem which yields a binomial coefficient number of combinations.

Consequently, it does appear that there may be no solution to this problem.

If the elements were sorted, then this problem would have been a merged list where we pick the element in the destination based on the smaller element from the first and the second array.

To make a choice of picking one element from one of the arrays, we need to sequentially visit the elements in both arrays. We advance one element in either array each time. In order to do so, our choice has to be in the same order as the master sequence.

We may give some weight to the choice of the element in both arrays. This assignment of weight has to factor in the index of the element if available from both arrays. For example the number 4 appears in both arrays above but since the index is lower in the second array rather than the first array, it will be picked  and the other 4 will be ignored. Moreover, the first few elements of the first subsequence before the number 4 in the first array will be picked before the element 4 in the second array is encountered. We could use this availability of duplicates as a way to progress as long as there are sufficient duplicates in both indicating the choice of the array.

Therefore if the element 7 in the above subsequence was preceded by a 3, the elements in the master sequence could have been reconstructed to the point of 1,3,7,2,4.