1
$\begingroup$

This algorithm works on a table of n choose k values for each k. e.g. for n = 4 the table looks like

a b c               k = 1 d --- min(a,b) min(a,c) min(a,d)        k = 2 min(b,c) min(b,d) min(c,d) --- min(a,b,c) min(a,b,d)      k = 3 min(a,c,d) min(b,c,d) --- min(a,b,c,d)    k = 4 

Everything is written in lexicographic ordering

Now I need to get answers for $a,b,c,d$. To get my answer for say 'a', I take each combination that contains 'a' and add them as such:

M('a') = \left[ {\begin{array}{c} min(a,b) + min(a,c) + min(a,d) - (min(a,b,c) + min(a,b,d) + min(a,c,d) - (min(a,b,c,d))) \\ min(a,b,c) + min(a,b,d) + min(a,c,d) - 2 * min(a,b,c,d) \\ min(a,b,c,d) \\ \end{array} } \right]

This is for row one, taking the sum of all mins that contain 'a' where k = 1, subtracting that sum from the sum of all mins containing 'a' where k = 3 which itself it subtracted from the last k = 4 value.

For row two taking the sum of all mins containing 'a' where k = 3 subtracted from the k = 4 layer twice. And row three is left alone.

This equation actually works out to be equivalent to sorting $min(a,b), min(a,c), min(a,d)$ in descending order, and works for any n and any letter an answer is required for. e.g. if $b < c < d < a$,

M('a') = \left[ {\begin{array}{c} d \\ c \\ b \end{array} } \right]

Can someone help explain why this algorithm ends up simply sorting the values that contain 'a' in the second layer in descending order?

  • 0
    I don't fully understand your $M$ thingamajiggie (isn't it a $k=2,3,4$ in your example, not $k=1,3,4$; how does the form generalize to arbitrary $n$?) but part of the answer probably involves an argument by symmetry. I.e. assume without loss of generality that a>b>c>d>e>\cdots and then work out $M(a)$, $M(b)$, and so forth explicitly.2011-07-22

1 Answers 1

2

Suppose wlog that all numbers are positive integers. Identify a number $x$ with the set $S(x) = \{1,\ldots,x\}$. We have $x = |S(x)|$ and $S(\min(x,y,\ldots)) = S(x) \cap S(y) \cap \cdots$. Your formula looks suspiciously like the inclusion-exclusion principle. My guess is that this correspondence can help you understand the algorithm.

  • 0
    Thanks for pointing me to the inclusion-exclusion principle, looks like I can explain it with that, as then my formula is equivalent to taking the union or maximum value per selected combinations containing 'a' per k layer.2011-07-22