algorithm - 识别重复序列中的缺口

Question

我有一个向量，应该包含从 00 到 11 的 n 个序列

A = [00;01;02;03;04;05;06;07;08;09;10;11;00;01;02;03;04;05;06;07;08;09;10;11]

我想检查序列“00 - 11”是否始终得到遵守(没有缺失值)。

例如如果

A =[00;01;02;  04;05;06;07;08;09;10;11;00;01;02;03;04;05;06;07;08;09;10;11] 

(第 3 个位置缺少 03)对于每个缺失值，我想在另一个向量中返回此信息

missing=
 [value_1,position_1;
 value_2, position_2;
 etc, etc]

你能帮帮我吗？

Answer 1

当然我们知道最后一个元素必须是 11，所以我们已经可以检查这一点并让我们的生活更容易测试所有前面的元素。我们确保 A 以 11 结尾，因此“逐元素更改”方法(如下)将是有效的。请注意，一开始也是如此，但在那里更改 A 会弄乱索引，所以我们最好稍后再处理。

missing = [];
if A(end) ~= 11
    missing = [missing; 11, length(A) + 1];
    A = [A, 11];
end

然后我们可以计算从一个元素到另一个元素的变化 dA = A(2:end) - A(1:end-1);，并确定间隙位置 idx_gap =查找((dA~=1) & (dA~=-11));.现在我们需要扩展所有缺失的索引和期望值，使用 ev 作为期望值。 ev可以从之前的值中得到，如

for k = 1 : length(idx_gap)
    ev = A(idx_gap(k));

现在，要填充的元素个数是该位置的变化dA减一(因为一表示没有间隙)。请注意，如果段之间的边界处存在间隙，这可以覆盖，因此我们使用模数。

    for n = 1 : mod(dA(idx_gap(k)) - 1, 12)
        ev = mod(ev + 1, 12);
        missing = [missing; ev, idx_gap(k) + 1];
    end
end

作为测试，考虑 A = [5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 0 1 2 3 4 6 7 8]。在这种情况下，从一开始的特殊初始化就会触发，已经记住丢失的 11，并将 A 更改为 [5 6 ... 7 8 11]。 missing then will yield

11    24    % recognizes improper termination of A.
11     7
 0     7    % properly handles wrap-over here.
 1     7
 2     7
 5    21    % recognizes single element as missing.
 9    24
10    24

这应该是您所期望的。现在缺少的仍然是 A 的开头，所以假设 missing = [0 : A(1) - 1, 1; missing]; 完成列表。