Given two arrays of positive numbers, re-arrange them to form a resulting array, resulting array contains the elements in the same given sequence

Question

An Example for more clearer Understanding.

Let

Array A - [1,2]

Array B - [3,4]

Resulting Array- [1,2,3,4], [1,3,2,4], [1,3,4,2], [3,4,1,2], [3,1,4,2], [3,1,2,4]

The resulting array contains the elements of A, B in the same sequence as it was given. ( 2 always comes after 1 and 4 always comes after 3 ) We have to print the total number of possible combinations to get the resulting array.

In this case its 6.

Note: Array elements are given in increasing order, It should appear in the same order in resulting array.

I think I can use DP here but I'm not sure,

Eg. base case would be, if any of the array is empty then there is only one possible resulting array, the non-empty array itself. But I'm not able to proceed on this base case. Any guidance would be deeply appreciated. Well, I'm even sure if DP is appropriate here, Perhaps if there is any other possible way to get to the solution.

No, it's not a homework.

Answer 1

Let the number of elements of A be M, and let the number of elements of B be N. An output array is uniquely determined by which of the M+N positions in the array are filled by elements of A. We can generate all possible choices of M out of M+N positions, and for each choice, assign the elements of A to those positions, assign the elements of B to the other positions, and output the array. For example, in Python:

import itertools
def merges(a, b):
    output_len = len(a) + len(b)
    for positions in itertools.combinations(range(output_len), len(a)):
        position_set = set(positions)
        a_iter, b_iter = iter(a), iter(b)
        yield [next(a_iter) if i in position_set else next(b_iter)
               for i in xrange(output_len)]