8
$\begingroup$

Suppose that, for a real application, I have ended up with a sorted list A = {$a_1, a_2, ..., a_{|A|}$} of elements of a certain kind (say, Type-A), and another sorted list B = {$b_1, b_2, ..., b_{|B|}$} of elements of a different kind (Type-B), such that Type-A elements are only comparable with Type-A elements, and likewise for Type-B.

At this point I seek to count the following: in how many ways can I merge both lists together, in such a way that the relative ordering of Type-A and Type-B elements, respectively, is preserved? (i.e. that if $P_M(x)$ represents the position of an element of A or B in the merged list, then $P_M(a_i)<P_M(a_j)$ and $P_M(b_i)<P_M(b_j)$ for all $i<j$)

I've tried to figure this out constructively by starting with an empty merged list and inserting elements of A or B one at a time, counting in how many ways each insertion can be done, but since this depends on the placement of previous elements of the same type, I've had little luck so far. I also tried explicitly counting all possibilities for different (small) lengths of A and B, but I've been unable to extract any potential general principle in this way.

$\endgroup$
1

3 Answers 3

15
$\begingroup$

The merged list has length $|A|+|B|$. Once you know which $|A|$ positions in it are occupied by the elements of list A, you also know exactly how the whole thing has to be ordered, since the internal orders of the elements of A and the elements of B are already known. Thus, there are $$\binom{|A|+|B|}{|A|}=\binom{|A|+|B|}{|B|}$$ possible merged lists, one for each choice of $|A|$ positions for the elements of list A.

$\endgroup$
5
  • $\begingroup$ Great answer! I've made an impl in C++ that generates all possible interleaved combinations of two lists, while maintaining relative order for anyone who is interested: github.com/domfarolino/algorithms/tree/master/src/… $\endgroup$ Oct 22, 2018 at 20:37
  • $\begingroup$ Can this further generalize to 3 lists? To 4? To N? $\endgroup$ May 27, 2021 at 15:54
  • $\begingroup$ Indeed, I believe this can further generalize to N lists, by viewing the overall operation as a series of (N-1) merges, so the total number of merged lists is computed as the product of (N-1) Binomial Coeffecients, where the i-th expression computes the selection of the positions of the i-th lists's elements from the available positions left after the first (i-1) lists have already been merged. $\endgroup$ May 27, 2021 at 21:38
  • 1
    $\begingroup$ @BryanPendleton: Yes: it’s a multinomial coefficient, $$\binom{|A_1|+|A_2|+\ldots+|A_N|}{A_1,A_2,\ldots,A_N}\,,$$ which can be expanded as a product of binomial coefficients as shown at the link. $\endgroup$ May 28, 2021 at 3:57
  • $\begingroup$ Great answer. Since we have to keep the relative ordering. This question is equal to "How many different ways are there to select n positions from m + n positions?“ $\endgroup$
    – Windsooon
    Sep 17, 2021 at 5:47
3
$\begingroup$

$\frac{(m+n)!}{(m)!(n)!}$; where m,n is the length of the arrays. $(m+n)!$ is the total number of ways of arranging without any restriction. The condition given that you can not change the order of each array so you should not change the order of each array , so we need to divide all the permutations of each array!

$\endgroup$
0
1
$\begingroup$

For merging N sorted lists, here is a good way to see that the solution is $$\frac{(|A_1|+\dots|+|A_N|)!}{|A_1|!\dots |A_N|!}$$

All the $(|A_1|+\dots|+|A_N|)$ elements can be permuted in $(|A_1|+\dots|+|A_N|)!$ ways. Among these, any solution which has the ordering of the $A_1$ elements different from the given order have to be thrown out. If you keep the positions of everyone except $A_1$ fixed, you can generate $|A_1|!$ permutations by shuffling $A_1$. Only 1 among these $|A_1|!$ solutions is valid. Hence the number solutions containing the right order of $A_1$ is $$\frac{(|A_1|+\dots|+|A_N|)!}{|A_1|!}$$

Now repeat the argument for $A_2$, $A_2, \dots A_N$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy