ddmin と 1-最小性

$c$ を相異なる要素の列、$\mathrm{fails}$ を $c$ の部分列に対して「テストが失敗する」かどうかを答える述語とし、$\mathrm{fails}(c)$ は真、空の列については偽とする。失敗する部分列 $c'$ が 1-最小であるとは、$c'$ からどの 1 要素を取り除いた列も失敗しないことをいう。

ddmin は、現在の列 $c$（最初は入力全体）と粒度 $g$（最初は $2$）をもち、$c$ の長さが $2$ 以上のあいだ次を繰り返す。$c$ を、長さがほぼ等しい $g$ 個の連続した塊 $\Delta_1, \ldots, \Delta_g$ に分ける（$\Delta_i$ は $c$ の $\lfloor |c|(i-1)/g \rfloor$ 番目から $\lfloor |c| i/g \rfloor$ 番目の手前まで）。

• (a) ある $\Delta_i$ が失敗するなら、最初のそれを新しい $c$ とし、$g = 2$ とする。
• (b) そうでなく、ある補集合 $c \setminus \Delta_i$ が失敗するなら、最初のそれを新しい $c$ とし、$g$ を $\max(g - 1, 2)$ にする。
• (c) そうでなく、$g \lt |c|$ なら、$g$ を $\min(|c|, 2g)$ にする。
• (d) そうでなければ（$g \ge |c|$）、繰り返しをやめる。

最後の $c$ を返す。