CODEWITHSUNDEEP
pythonarraysalgorithm
Yousef
Yousef

Reputation: 500

iterate array with shrinking fair window

I couldn't choose the right title but what I want is to solve this puzzle:

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

Puzzle: I have a length L, I want to make sure that this array satisfy this condition for L

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

where window is any possible distance between two values of this array, for this I will have to have i (start element), j (last element), and slid them fairly to cover all possible combinations. And it should because the array is sorted.
for example, this is my trial of tackling this problem:

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 ;;

I didn't find a specific pattern here, I think there is a better way to solve this problem. And I really feel like there is a popular algorithm for this but for some reason, I completely forgot about it.

EDIT: to clarify, these are starting indexes of a string pattern in a very long string (DNA), what I'm trying to find here is:
a string pattern in a long string that is appearing many times (t) within a window of length L. I forgot to mention that each slide will result in the frequency of a pattern to decrease, meaning the length of arr becomes arr - 1, so we have to check if len(arr) is still < t, if it is, we return False if we haven't found that window and returned true

Example: When L = 500, frequency = 16 (len(arr)), and t = 14 (already set), freq>t? yes, then we see arr[-1] - arr[0] = 465 which is < 500. True!

But when L = 400,frequency = 16, and t = 14, arr[-1] - arr[0] = 465 which is > 400. False!
We try again with arr[-2] - arr[0] = 426, and still freq=16>t=14
We try again with arr[-1] - arr[1] = 448, and still freq=16>t=14
We try again with arr[-2] - arr[1] = 393, Correct? no, freq=14 == t=14
we return false

Upvotes: 2

Views: 96

Answers (1)

Raja G
Raja G

Reputation: 6633

By using zip you can achieve the combinations that will give distance between two points with less than L(=50) length.

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]:

Upvotes: 0

Related Questions