覆盖数组

覆盖数组（covering array）是使任意指定数量的因素列都包含全部水平组合的试验表。每行表示一次试验，每列表示一个因素；强度为 $t$ 时，任取 $t$ 列，每种可能的 $t$ 元组合都至少出现一次。

与正交表相比，覆盖数组允许某些组合多出现几次，不要求完全均衡。这适合检查“所有两因素设置是否都试过”等覆盖问题，但不能据此保证全部高阶交互已经测试，或保证被测系统没有缺陷。

定义与试验数

对 $1\le t\le k$、$v\ge 2$，一个 $\mathrm{CA}(N;t,k,v)$ 是 $N\times k$ 表，元素取自 $v$ 种水平，任意 $t$ 列的行投影都覆盖全部 $v^t$ 个有序元组。本文各因素水平数相同，且暂不设组合间的约束。文献也使用不同参数顺序，应据定义核对。

固定任意 $t$ 列，每行只能提供其中一个元组，故必有 $N\ge v^t$。但同一行要同时为许多列组服务，这个基本下界未必能达到。给定 $t,k,v$ 后的最小行数，常记为 $\mathrm{CAN}(t,k,v)$。

全因子表含有全部 $v^k$ 行，必定覆盖所有阶数不超过 $k$ 的组合。覆盖设计希望在较小强度 $t$ 下减少行数；减少的是所保证的联合范围，不能将它称为“完成全部状态测试”。

五行覆盖四个二水平因素

设四个因素编号 $A,B,C,D$，水平为零、一。取全一行，再取四个单位向量行： $$T=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right).$$ 任选两列 $i,j$：全一行提供 $11$，第 $i$ 个单位向量行提供 $10$，第 $j$ 个提供 $01$，其余两个单位向量行提供 $00$。故每一对列都包含全部四种组合，得到 $\mathrm{CA}(5;2,4,2)$。

每组两列中，00 出现两次，01、10、11 各一次。因此它覆盖全部二因素组合，却不是指数相同的强度二正交表。

四行不可行的证明

若四行能覆盖四个二水平因素的所有二列组合，则对每一对列，四种组合必须各出现一次，因而这会是一张 $\mathrm{OA}(4,4,2,2)$。

把零改成负一、一保持为一。每列都含两个负一和两个一，与全一向量正交。任意两列的逐行乘积也含两个负一和两个一，所以两列互相正交。这样便在 ${ℝ}^4$ 中得到四个因素列和一个全一列，共五个非零且两两正交的向量；它们必线性无关，与空间维数四矛盾。

故至少需要五行，而前面的构造确实使用五行，得到 $\mathrm{CAN}(2,4,2)=5$。这里给出了上下界相同的完整证明，不是仅因计算程序找到一个五行设计便宣布最优。

二因素覆盖不包含三因素覆盖

在上述表的前三列中，只出现 $$111,100,010,001,000.$$ 例如 $110$ 没出现。因此若某个问题仅在 $A=1,B=1,C=0$ 时触发，这五行不会检测到它，尽管任意两个因素的每一种设置都已出现。

强度是明确的保证范围。提高强度通常增加所需试验数，不能靠重复已有行补上原来从未出现的三因素组合。

变式。 去掉全一行，只保留四个单位向量行。任取两列，$00,01,10$ 仍出现，但 $11$ 不再出现，因而不再是强度二覆盖数组。每一列仍含两种水平，说明单因素覆盖不够。

可运行的覆盖检查

以下函数检查无约束、同水平数的输入表；若存在缺失组合，返回第一组未覆盖完整的列指标。它不生成最小设计，也不修改输入。

Python 3

from itertools import combinations


def covering_check(array, levels, strength):
    rows = [tuple(row) for row in array]
    if type(levels) is not int or levels < 2 or not rows:
        raise ValueError("Need rows and at least two levels")
    width = len(rows[0])
    if (type(strength) is not int or not 1 <= strength <= width
            or any(len(row) != width for row in rows)):
        raise ValueError("Invalid dimensions or strength")
    if any(type(x) is not int or not 0 <= x < levels
           for row in rows for x in row):
        raise ValueError("Invalid level")
    for columns in combinations(range(width), strength):
        seen = {tuple(row[j] for j in columns) for row in rows}
        if len(seen) != levels ** strength:
            return False, columns
    return True, None


table = [[1, 1, 1, 1], [1, 0, 0, 0], [0, 1, 0, 0],
         [0, 0, 1, 0], [0, 0, 0, 1]]
print(covering_check(table, 2, 2))
print(covering_check(table, 2, 3))
print(covering_check(table[1:], 2, 2))
# (True, None)
# (False, (0, 1, 2))
# (False, (0, 1))

因所有元素都在合法水平集中，一个投影至多包含 $v^t$ 个不同元组；当它有恰好这么多个时，正好穷尽全部可能。因此检查集合大小就是定义的完整判定。按散列表平均成本计，检查时间为 $O\left((\genfrac{}{}{0ex}{}{k}{t})Nt\right)$，复制表占 $O(Nk)$ 空间，单次投影的集合至多保存 $min(N,v^t)$ 个长度 $t$ 的元组。检查容易，并不表示寻找最少行数同样容易。

约束、重复与应用边界

实际因素可能有不同水平数，例如浏览器三类、权限两类、语言四类。这需要混合水平覆盖数组；每组列应覆盖的组合数由这些列水平数的乘积决定，不能继续一律使用 $v^t$。

因素间还可能存在禁用组合。若规定 $A=B$，则两因素的 $01,10$ 本就不可实现；目标应改为所有可行完整配置所诱导的可行低阶元组。直接从一张无约束覆盖表中删除非法行，可能同时删掉某些本可实现的低阶组合，因而必须重新检查覆盖。

重复某一行不会增加已经覆盖的元组种类，却可能服务于重复测量或可靠性分析。覆盖表只安排了“试哪些输入”；观测什么、怎样判断失败、运行是否可重复，以及高阶相互作用是否重要，仍属于试验或测试方案的其他部分。