0

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.

nitte93
  • 1,820
  • 3
  • 26
  • 42
  • Do you actually need to produce all possible result arrays, or do you just need to return the number of possible arrays? Either way, it's straightforward combinatorics, but even for small input, there can be far too many arrays to produce all of them. – user2357112 Jun 07 '15 at 00:33
  • I have to print the combinations as well as the number of this possible combinations. – nitte93 Jun 07 '15 at 00:36
  • How much library code are you allowed to use? Something like Python's [`itertools.combinations`](https://docs.python.org/2/library/itertools.html#itertools.combinations) or C++'s [`std::next_permutation`](http://stackoverflow.com/questions/9430568/generating-combinations-in-c) would trivialize the problem. – user2357112 Jun 07 '15 at 00:44
  • There is no restriction to that, but how do you suggest to arrange them in such a order such that they follow the constraints of the resulting array. As the permutation will output all the possible combinations. – nitte93 Jun 07 '15 at 00:53
  • BTW, Thanks for next_permutation, wasn't aware of it. Make my job easier in so many other cases. – nitte93 Jun 07 '15 at 00:56
  • You can make an array of 0s and 1s representing which positions of the output get elements of A and which positions get elements of B, then use next_permutation to get all possible permutations of that array. (There's a bit of a complication in that next_permutation has poor asymptotic complexity when the input is almost all the same value, for example, if A has length 1 and B has length 1000, but it isn't any worse than the complexity of printing the output.) – user2357112 Jun 07 '15 at 01:38

1 Answers1

0

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)]
user2357112
  • 260,549
  • 28
  • 431
  • 505