Compute Meet in Dominance Order

I need to compute the meet of two partitions $\lambda=(\lambda_1,\ldots,\lambda_r)$ and $\mu=(\mu_1,\ldots,\mu_s)$ with respect to the dominance order. It's not a difficult thing to do and might be considered an oddity by most of you, but that doesn't bother me.

Let $\varrho:=\lambda\vartriangle\mu$ be the meet of $\lambda$ and $\mu$. We Compute a partition $\alpha$ by setting $\alpha_1:=\min(\lambda_1,\mu_1)$ and recursively setting $\alpha_{i+1} := \min\left{\scriptstyle\begin{array}{l} (\lambda_1+\cdots+\lambda_{i+1})-(\alpha_1+\cdots+\alpha_i),\ (\mu_1+\cdots+\mu_{i+1})-(\alpha_1+\cdots+\alpha_i), \ \alpha_i \end{array}\right}.$

Fundamental Theorem of computing the Meet in the Dominance Order. $\alpha=\varrho$.

Proof. First, $\alpha \trianglelefteq \lambda$ and $\alpha\trianglelefteq\mu$ holds for obvious reasons: To show e.g. that for all $i$, we have $\alpha_1+\cdots+\alpha_i \le \lambda_1+\cdots+\lambda_i,$ we induct on $i$ with $i=1$ being trivial and the induction step also follows immediately from the definition. Therefore, to show that $\alpha=\varrho,$ we simply need to show that $\varrho\trianglelefteq\alpha.$ If this is the case, then we must have $\varrho=\alpha$ by definition of the meet. Again, we induct on $i$. For $i=1$, we have $\varrho_1\le\lambda_1$ and $\varrho_1\le\mu_1,$ so we also have $\varrho_1\le\min(\lambda_1,\mu_1)=\alpha_1.$ In the induction step, we assume $\alpha_1+\cdots+\alpha_i + d_i = \varrho_1+\cdots+\varrho_i$ for some $d_i \ge 0$. Hence, $\alpha_1 + \cdots + \alpha_i + \varrho_{i+1} + d_i = \varrho_1 + \cdots + \varrho_{i+1} \le \lambda_1 + \cdots + \lambda_{i+1}$ and it follows that $\varrho_{i+1} + d_i \le (\lambda_1+\cdots+\lambda_{i+1})-(\alpha_1+\cdots+\alpha_i) = \alpha_{i+1},$ in other words $\varrho_{i+1} \le \alpha_{i+1}$ which implies $\varrho_i + \cdots + \varrho_{i+1} \le \alpha_1 + \cdots + \alpha_{i+1}$ by again using the induction hypothesis. This concludes the proof. QED.

Python Implementation

>>> def dominanceMeet(p,q):
...     n = max( sum(p), sum(q) )
...     a = []
...     sp, sq, sa, prev, i = 0, 0, 0, n, 0
...     while prev:
...         sp += p[i] if i < len(p) else 0
...         sq += q[i] if i < len(q) else 0
...         prev, i = min(sp-sa, sq-sa, prev), i+1
...         sa += prev
...         if prev: a.append(prev)
...     return a
...
>>>
>>>
>>> dominanceMeet([3,1,1,1],[2,2,2])
[2, 2, 1, 1]
>>>

The code is written in a quite imperative style. That's because it's going to be C code rather soon.