Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspxHere'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,Yen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7329810Wed, 30 Jan 2008 20:33:14 GMT91d46819-8472-40ad-a661-2c78acb4018c:7329810Luntain<p>> what's "length of the not shorter list" mean? </p>
<p>In most cases it is the length of the longer list, except when two lists have the same size. </p>
<p>Allow me to write:</p>
<p>n - length of the longer list</p>
<p>m - length of the shorter list</p>
<p>number of combinations is sum from k=1 to k=m of (n+1 choose k)</p>
<p>where (n choose k) = n!/[(n-k)!*k!]</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7329810" width="1" height="1">my solutionhttp://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7329097Wed, 30 Jan 2008 19:48:30 GMT91d46819-8472-40ad-a661-2c78acb4018c:7329097Mike Stall - MSFT<p>The way we ended up solving it was:</p>
<p>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.</p>
<p>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) ). </p>
<p>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. </p>
<p>My wife was writing out the numbers and putting them in a NxM table, and I recognized </p>
<p>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. </p>
<p>C(n,r) has summation identities, which play into the summation formulas that some of the folks came up with.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7329097" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7328112Wed, 30 Jan 2008 18:27:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:7328112Raymond Chen - MSFT<p>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).</p>
<p>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.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7328112" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7327467Wed, 30 Jan 2008 17:47:04 GMT91d46819-8472-40ad-a661-2c78acb4018c:7327467David Srbecky<p>I forgot to say why the recursive formula is </p>
<p>f(m,n) = f(m-1,n) + f(m,n-1)</p>
<p>f(0,n) = 1</p>
<p>f(m,0) = 1</p>
<p>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.</p>
<p>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.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7327467" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7327124Wed, 30 Jan 2008 17:21:23 GMT91d46819-8472-40ad-a661-2c78acb4018c:7327124David Srbecky<p>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.</p>
<p>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).</p>
<p>----</p>
<p>The recursive formula for the computation is f(m,n) = f(m-1,n) + f(m,n-1) plus base case. </p>
<p>Notice its similarity to Pascal's rule (<a rel="nofollow" target="_new" href="http://en.wikipedia.org/wiki/Pascal%27s_rule">http://en.wikipedia.org/wiki/Pascal%27s_rule</a>).</p>
<p>----</p>
<p>The problem is a bit similar to Levenshtein's edit distance algorithm (<a rel="nofollow" target="_new" href="http://en.wikipedia.org/wiki/Levenshtein_distance">http://en.wikipedia.org/wiki/Levenshtein_distance</a>) 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.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7327124" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7312606Tue, 29 Jan 2008 23:58:35 GMT91d46819-8472-40ad-a661-2c78acb4018c:7312606Roberto<p>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).</p>
<p>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.</p>
<p>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.</p>
<p>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).</p>
<p>We continue to do this until no columns are left. The number of solution will be:</p>
<p>f(N+1,M) = f(N,M) + f(N,M-1) + ... + f(N,0)</p>
<p>With f(N,0) = 1 for any N, since with only one list there's only one solution (the sorted list).</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7312606" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7311179Tue, 29 Jan 2008 22:07:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:7311179Mike Stall - MSFT<p>Bruno - right on and nice explanation.</p>
<p>Roberto - can you explain how you landed at your answer?</p>
<p>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.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7311179" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7306742Tue, 29 Jan 2008 17:53:33 GMT91d46819-8472-40ad-a661-2c78acb4018c:7306742Bruno Gomes<p>Since the comments are moderated, I'll send my approach to solve this one.</p>
<p>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!)</p>
<p>As an example: F(6,4) = (6+4)!/(6!*4!) = (10*9*8*7)/(4*3*2*1) = 210</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7306742" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7304970Tue, 29 Jan 2008 15:25:15 GMT91d46819-8472-40ad-a661-2c78acb4018c:7304970Roberto<p>An iterative solution:</p>
<p>f(1,1) = 2</p>
<p>f(N,M) = f(M,N) = 1 + [f(N-1,M) + f(N-1,M-1) + ... + f(N-1,1)]</p>
<p>So:</p>
<p>f(3,2) = 1 + f(2,2) + f(2,1)</p>
<p>f(2,1) = 1 + f(1,1) = 3</p>
<p>f(2,2) = 1 + f(1,2) + f(1,1) = 1 + 3 + 2 = 6</p>
<p>f(3,2) = 1 + 6 + 3 = 10</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7304970" width="1" height="1">re: Quiz: can you count how many combinations ...http://blogs.msdn.com/b/jmstall/archive/2008/01/28/quiz-can-you-count-how-many-combinations.aspx#7304686Tue, 29 Jan 2008 15:06:41 GMT91d46819-8472-40ad-a661-2c78acb4018c:7304686Luntain<p>Is that correct? (ROT13)</p>
<p>a - yratgu bs gur abg fubegre yvfg</p>
<p>z - yratgu bs gur abg ybatre yvfg</p>
<p>ahzore bs pbzovangvbaf vf fhz sebz x=1 gb x=z bs (a+1 bire x)</p>
<p>jurer (a bire x) = a!/[(a-x)!*x!]</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=7304686" width="1" height="1">