2


I have a numpy array (in Python 3) and I'd like to find a sub-vector in it.
If I search for a full vector, this code works:

import numpy as np

a = np.zeros([10,5])
a[0] = [5,6,4,8,5]
a[1] = [3,6,8,5,3]
a[2] = [3,2,1,5,3]
a[3] = [6,5,6,4,6]
a[4] = [3,4,7,6,3]
a[5] = [2,3,1,5,2]
a[6] = [1,1,3,2,1]
a[7] = [6,5,8,8,6]
a[8] = [5,4,9,7,5]
a[9] = [1,2,7,8,1]

print(a)
search = [2,3,1,5,2] # correctly returns 5
i = np.argwhere(np.all((a-np.array(search))==0, axis=1))
print(int(i))

Ok, but I'd like to find this sub-vector:

search = [2,3,1,5]

How can I find it?

Improve this question
2
  • So it has to be contiguous, or can it have gaps? For example is [2,3,1,_,5] a valid vector for the subvector? It is always a prefix? Commented Apr 19, 2020 at 11:44
  • It has to be contiguous, but not always a prefix. It can be anywhere, say [2,7]. Commented May 7, 2020 at 20:12

3 Answers 3

Reset to default
1

Simple numpy solution:

Search the raveled array and stop in first occurrence (you will be able to modify this into any type of search you deem fit including if your search list spans over multiple rows AND also finding multiple occurrences of search in a).

Following code assumes you are looking for first occurrence within a row of a:

for i in range(a.size-len(search)):
    if np.array_equal(np.ravel(a)[i:i+len(search)], np.array(search)) and int(i/a.shape[1])==int((i+len(search)-1)/a.shape[1]):
        print(int(i/a.shape[1]))
        break

If speed matters and a/search is large, save a raveled version of a into a_ravel = np.ravel(a) and numpy array of np.array(search) and use that inside the for loop.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Here is one way,

EDIT : The following code assumes your search vector starts at the beginning of the row

import numpy as np

a = np.zeros([10,5])
a[0] = [5,6,4,8,5]
a[1] = [3,6,8,5,3]
a[2] = [3,2,1,5,3]
a[3] = [6,5,6,4,6]
a[4] = [3,4,7,6,3]
a[5] = [2,3,1,5,2]
a[6] = [1,1,3,2,1]
a[7] = [6,5,8,8,6]
a[8] = [5,4,9,7,5]
a[9] = [1,2,7,8,1]
search = [2,3,1,5]

s = search+[None]*((a.shape[1]-len(search)))
loc = np.where((a==s).sum(1)== len(search))

Output 

loc 
(array([5], dtype=int64),)
Improve this answer

5 Comments

I like the idea, but this doesn't quite work. If a[5]= [2,3,1,5,0] this would have failed. Maybe loc = np.where((a==s).sum(1) >= len(search))?
Unfortunately, this would also have failed if search = [3, 1] and a[5] = [2,5,1,0,0]. You'd have got a false match here because of the padding of zeros.
You could pad with np.nans instead. but then you're still assuming that the vector we're looking for starts at the beginning of a row, ie. we would have failed if a[5] = [7,2,3,1,5] even though it contains our search pattern
@Ralph Well spotted! In this case replacing the 0 with None should do. Try it out and see !
@Ralph yes that's correct, np.nan could also do, And yes the code assumes vector starts at the beginning of a row. I'll add that now
0 
import numpy as np

a = np.zeros([10, 5])
a[0] = [5, 6, 4, 8, 5]
a[1] = [3, 6, 8, 5, 3]
a[2] = [3, 2, 1, 5, 3]
a[3] = [6, 5, 6, 4, 6]
a[4] = [3, 4, 7, 6, 3]
a[5] = [2, 3, 1, 5, 2]
a[6] = [1, 1, 3, 2, 1]
a[7] = [6, 5, 8, 8, 6]
a[8] = [5, 4, 9, 7, 5]
a[9] = [1, 2, 7, 8, 1]

search = [2, 3, 1, 5]
for i, row in enumerate(a):
    strided_row = np.lib.stride_tricks.as_strided(
        row, (a.shape[1] - len(search) + 1, len(search)), (a.itemsize, a.itemsize)
    )
    if (strided_row == search).all(axis=1).any():
        break
else:
    i = None
print(i)

Assuming that search is contiguous part of some row of a. Documentation for as_strided(). For example for the first row: strided_row is [[5, 6, 4, 8], [6, 4, 8, 5]] then we can search for search the same way as in question.

Improve this answer

2 Comments

Any reason you set i = None before the enumerate?
I want to handle situation when there is no search in a and do it wrongly). I edit answer. Thanks.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.