Here’s a combinatorics quiz:

*If you have 2 ordered lists (lengths N, M), how many ways can they be interleaved into a single list while still preserving the partial ordering from the original lists?*

So if the lists were:

List 1: A,B

List 2: X,Y

The following would be valid:

- A,B,X,Y

- A,X,Y,B

- X,Y,A,B

- A,X,B,Y

But ‘ yxab’ would be invalid since it lists y before x, and the original list ‘xy’ says y must come after x.

For the full quiz effect, stop reading now and go figure it out! I’ll leave the comments moderated so that folks don’t give things away. (**[Update Jan 29] **I published the answers) : Read on for hints.

————-

My wife and I just worked it through and came up with an answer. Our approaches highlighted our different personalities. She started listing out examples while I started by looking for isomorphisms to more easily countable patterns. I ended up seeing an isomorphism in her examples and we found the solution together.

To verify our answer, I wrote some Python code (run with IronPython) to go through brute-force and count. So the function t(na,nb) enumerates all orderings between 2 lists of sizes na and nb. In this case, the lists are (a0,a1,a2) and (b0,b1), and there are 10 ways of interleaving them.

>>> t(3,2) |

It does a dumb brute-force approach: enumerate all possible interleavings (which is huge) and then just take the ones that preserve the partial ordering (which is much smaller). While it’s dumb and slow, it’s more convincingly correct than some complex proof. (It optimizes for simplicity). Here’s the code:

# return a generator listing all orderings of l

# assumes all elements in l are unique

def combo(l):

#print ‘combo:’, l

if (len(l) == 1): yield l

for head in l:

rest = list(l)

rest.remove(head)

for x in combo(rest):

#print ‘x=’, x

yield ([head] + x)def verifyHelper(letter, all):

last = -1

for x in all:

if (x[0] == letter):

if x[1] <= last:

return False

last = x[1]

return True# verify that the sub sequences are in order

def verify(all):

return verifyHelper(‘a’, all) and verifyHelper(‘b’, all)# convert a schedule list to a string for pretty printing,

# eg: a1 b0 a2 b0

def s(l):

d = “”

for x in l:

d += (‘%s%d ‘ % (x[0], x[1]))

return d# Actual counter

def t(na, nb):

a = [(‘a’, i) for i in range(0, na)]

b = [(‘b’, i) for i in range(0, nb)]

all = combo(a + b)

total = 0

for x in all:

if (verify(x)):

print ‘valid=’, s(x)

total += 1

return total

Is that correct? (ROT13)

a – yratgu bs gur abg fubegre yvfg

z – yratgu bs gur abg ybatre yvfg

ahzore bs pbzovangvbaf vf fhz sebz x=1 gb x=z bs (a+1 bire x)

jurer (a bire x) = a!/[(a-x)!*x!]

An iterative solution:

f(1,1) = 2

f(N,M) = f(M,N) = 1 + [f(N-1,M) + f(N-1,M-1) + … + f(N-1,1)]

So:

f(3,2) = 1 + f(2,2) + f(2,1)

f(2,1) = 1 + f(1,1) = 3

f(2,2) = 1 + f(1,2) + f(1,1) = 1 + 3 + 2 = 6

f(3,2) = 1 + 6 + 3 = 10

Since the comments are moderated, I’ll send my approach to solve this one.

It’s a fairly simple combinatorial problem, actually. If you consider all the elements from both lists and disregard the constraint, the number of possible permutations is (m+n)!, where m and n are the number of items in each list. Now, the elements of each list can appear in m! and n! different ways in each permutation, but only one order is allowed for each. Thus, the function you are looking for is: F(m,n) = (m + n)! / (n!*m!)

As an example: F(6,4) = (6+4)!/(6!*4!) = (10*9*8*7)/(4*3*2*1) = 210

Bruno – right on and nice explanation.

Roberto – can you explain how you landed at your answer?

Luntain – what’s "length of the not shorter list" mean? I think you’re right, but the double negatives confused me a little in checking.

Ok, let me try to explain. Suppose we solved f(N,M), and we added one more element to the first list; we want to know f(N+1,M).

I can say without loss of generality that the additional element is bigger that any element of the list. If this is not the case, simply repeat f(N,M) leaving the biggest element out and adding the new element.

It’s clear that we can always add the new element to the end of the interleaved list, since it’s the biggest. So for each solution of f(N,M) we have one trivial solution for f(N+1,M) with the new element at the end.

Now, for some solutions of f(N,M), we can also add the new element to the second-last position of the interleaved list. We can do this on the solutions where the first list is already exhausted before the last column. These correspond to the problem of solving f(N,M-1), since we want the last column to contain only elements from the second list. If we remove this last column we’re essentially solving f(N,M-1).

We continue to do this until no columns are left. The number of solution will be:

f(N+1,M) = f(N,M) + f(N,M-1) + … + f(N,0)

With f(N,0) = 1 for any N, since with only one list there’s only one solution (the sorted list).

The combined list will contain some elements from list A and some elements from list B. For example, a list A of size 3 and a list B of size 5 could be mixed as follows: ABBABABB.

The number of possible outputs is the number of ways we can place 3 As in that string of length 8. That is, (8 choose 3) or in general (m+n choose n).

—-

The recursive formula for the computation is f(m,n) = f(m-1,n) + f(m,n-1) plus base case.

Notice its similarity to Pascal’s rule (http://en.wikipedia.org/wiki/Pascal%27s_rule).

—-

The problem is a bit similar to Levenshtein’s edit distance algorithm (http://en.wikipedia.org/wiki/Levenshtein_distance) except that we are interleaving strings rather then looking for similarities. The total number of combinations is the total number of possible paths though the lattice. This is again (m+n choose n) because at each cross point we can turn either right or down.

I forgot to say why the recursive formula is

f(m,n) = f(m-1,n) + f(m,n-1)

f(0,n) = 1

f(m,0) = 1

One interpretation is the Levenshtein-inspired one. The value of an element in the matrix is the total number of possible paths to that element. Base case is 1 possible path. All other numbers are calculated as the number of possible paths to the element above plus to the element on the left.

Other interpretation is based on the following construction. We have input lists of sizes m and n. Choose one of the input lists, remove its head and append it to the tail of output. Repeat until inputs are empty. The total number of combinations is f(m-1,n) + f(m,n-1) where f(m-1,n) is the total number of combinations left if we have chosen to remove element from the first list and f(m,n-1) if we have chosen to remove element from the second list.

You can solve this just by looking at it. All you’re really doing is choosing the next item from "List 1" N times and "List 2" M times. That’s the standard binomial coefficient C(M+N,N).

Note that this solution breaks down if the two lists have items in common. If List 1 is "A" and List 2 is "A,B", then there are only two results, not three.

The way we ended up solving it was:

The total interleaved list is length N+M. Since each list must stay well ordered, you just have choose the final spot in the entire list that list 1’s items will appear.

So Of that choose N slots that List 1 items will go into. That’s C(N+M, N) (which is also C(N+M,M) ).

Eg, if it’s N=2, M=3, the total combined list will be 5 long. So pick the 2 spots that list 1’s items will be.

My wife was writing out the numbers and putting them in a NxM table, and I recognized

that to be Pascal’s triangle. And then I recalled the relationship between Pascal’s triangle elements and C(n,r) and that got me to look at the problem in the right way.

C(n,r) has summation identities, which play into the summation formulas that some of the folks came up with.

> what’s "length of the not shorter list" mean?

In most cases it is the length of the longer list, except when two lists have the same size.

Allow me to write:

n – length of the longer list

m – length of the shorter list

number of combinations is sum from k=1 to k=m of (n+1 choose k)

where (n choose k) = n!/[(n-k)!*k!]