Iter-4360dd15-0169-fact-window-distance-predicate

迭代 169：插入位置 p 与相邻交换位置 i 的窗口距离判定

本轮把上一轮的经验性约束收紧成一个**可直接调用**的精确判定：

定义

- 设短串为 S，长度为 n。
- 先在 p ∈ [0, n] 处做一次插入，得到长度 n+1 的串 T。
- 再在 T 中选择相邻交换起点 i ∈ [0, n-1]，交换 T[i] 与 T[i+1]。
- 只允许满足窗口约束 |i - p| ≤ r 的交换；边界处自然截断。

这里的关键点是：**i 必须是插入后的字符串上的相邻交换起点**，不能把交换中心、交换后位置或全局索引混为一谈；否则窗口约束会被写歪。

精确判定式

对候选长串 L：

accept(S, L, r) := ∃ p ∈ [0,n], ∃ i ∈ [max(0,p-r), min(n-1,p+r)] : swap(insert(S,p), i) = L

其中 swap(X, i) 表示交换 X[i] 与 X[i+1]。

可复现代码

from itertools import product
def apply_insert_and_swap(short, p, i, marker='x'):
    long = list(short[:p]) + [marker] + list(short[p:])
    if not (0 <= i < len(long)-1):
        return None
    long[i], long[i+1] = long[i+1], long[i]
    return tuple(long)
def accepts_windowed_one_swap(short, long, r=1, marker='x'):
    n = len(short)
    if len(long) != n + 1:
        return False
    long = tuple(long)
    for p in range(n + 1):
        lo = max(0, p - r)
        hi = min(n - 1, p + r)
        for i in range(lo, hi + 1):
            if apply_insert_and_swap(short, p, i, marker) == long:
                return True
    return False

已验证样例

- short = ab, long = xba, r = 1 -> 通过；
- short = ab, long = bax, r = 1 -> 不通过；
- short = ab, long = bax, r = 2 -> 通过。

结论

如果想防止“局部插入”退化为“全局重排放行器”，窗口约束必须绑定到**插入后的相邻交换起点 i**，而不是对“是否发生过一次交换”做裸放行。