python - 使用缩小的公平窗口迭代数组

Question

我无法选择正确的标题，但我想要解决这个难题:

arr = [187, 220, 245, 265, 278, 321, 346, 360, 391, 407, 443, 492, 533, 557, 613, 652]

谜题:我有一个长度L，我想确保这个数组满足L的这个条件

window = arr[j] - arr[i]
if window <= L

其中 window 是该数组的两个值之间的任何可能距离，为此我必须有 i(起始元素)、j(最后一个元素)，并公平地滑动它们以覆盖所有可能的组合。它应该是因为数组已排序。
例如，这是我解决这个问题的尝试:

i = 0, j = -1 # initial values of i and j in python for first and last


i = 0, j = -1 # iteration 0 if(iter % 4 == 0): nothing
i = 1, j = -1 # iteration 1 if(iter % 4 == 1): i+=1
i = 0, j = -2 # iteration 2 if(iter % 4 == 2): i-=1; j-=1
i = 1, j = -2 # iteration 3 if(iter % 4 == 3): i+=1;


i = 2, j = -2 # iteration 4 ;;
i = 1, j = -3 # iteration 5 ;; 
i = 2, j = -3 # iteration 6 ;; 
i = 3, j = -3 # iteration 7 ;;

我这里没有找到具体的模式，我觉得有更好的方法可以解决这个问题。我真的觉得有一个流行的算法，但出于某种原因，我完全忘记了它。

编辑: 澄清一下，这些是一个很长的字符串 (DNA) 中字符串模式的起始索引，我想在这里找到的是:
在长度为 L 的窗口内出现多次 (t) 的长字符串中的字符串模式。我忘了说每张幻灯片都会导致模式的频率降低，这意味着 arr 的长度变为 arr - 1，所以我们必须检查 len(arr) 是否仍然 < t，如果是，我们返回 False如果我们没有找到那个窗口并返回 true

示例: 当L = 500, frequency = 16 (len(arr)), t = 14 (已经设置), freq>t?是的，然后我们看到 arr[-1] - arr[0] = 465 < 500。没错!

但是当 L = 400、频率 = 16 且 t = 14 时，arr[-1] - arr[0] = 465 即 > 400。错误!
我们再次尝试使用 arr[-2] - arr[0] = 426，仍然是 freq=16>t=14
我们再次尝试 arr[-1] - arr[1] = 448，仍然是 freq=16>t=14
我们再次尝试 arr[-2] - arr[1] = 393，对吗？不，频率=14 == t=14
我们返回false

Answer 1

通过使用 zip，您可以获得组合，使两点之间的距离小于 L(=50) 长度。

In [11]: [(x,y) for x, y in zip (arr, arr[1:]) if x - y <= 50 ]
Out[11]:
[(187, 204),
 (204, 245),
 (245, 265),
 (265, 278),
 (278, 321),
 (321, 346),
 (346, 360),
 (360, 391),
 (391, 407),
 (407, 443),
 (443, 492),
 (492, 533),
 (533, 557),
 (557, 613),
 (613, 652)]

In [12]: