다음을 통해 공유

Quiz: can you count how many combinations ...

  • 아티클

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:

  1. A,B,X,Y
  2. A,X,Y,B
  3. X,Y,A,B
  4. 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)valid= a0 a1 a2 b0 b1valid= a0 a1 b0 a2 b1valid= a0 a1 b0 b1 a2valid= a0 b0 a1 a2 b1valid= a0 b0 a1 b1 a2valid= a0 b0 b1 a1 a2valid= b0 a0 a1 a2 b1valid= b0 a0 a1 b1 a2valid= b0 a0 b1 a1 a2valid= b0 b1 a0 a1 a210

 

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

Comments

  • Anonymous
    January 28, 2008
    The comment has been removed

  • Anonymous
    January 28, 2008
    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

  • Anonymous
    January 29, 2008
    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!) = (10987)/(4321) = 210

  • Anonymous
    January 29, 2008
    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.

  • Anonymous
    January 29, 2008
    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).

  • Anonymous
    January 30, 2008
    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.

  • Anonymous
    January 30, 2008
    The comment has been removed

  • Anonymous
    January 30, 2008
    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.

  • Anonymous
    January 30, 2008
    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.

  • Anonymous
    January 30, 2008
    > 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!]