Найти все подмассивы фиксированной длины с заданным рейтингом

Question

У меня есть массив чисел, например:

A = [1, 5, 2, 4, 3]

и массив, который определяет ранг, например:

B = [0, 2, 1]

Моя цель - найти все подмассивы A, которые "подчиняются" рангу B. Если подмассив подчиняется рангу, это означает, что i-й наименьший элемент подмассива должен иметь B[i] в качестве своего (подмассива) индекс. Таким образом, для соответствия подмассива наименьший элемент внутри него должен быть в позиции 0, второй наименьший элемент должен быть в позиции 2, а самый большой элемент должен быть в позиции 1.

Так, например, здесь есть два подмассива A, которые соответствуют ранжированию: [1, 5, 2] (потому что A [0]

До сих пор мне удалось найти решение, которое имеет O(mn) (m is len (A) и n is len (B)) временную сложность, оно перебирает все подмассивы длины 3 и проверяет, они правильно упорядочены:

A = [1, 5, 2, 4, 3]
B = [0, 2, 1]
m = len(A)
n = len(B)
for i in range(m - n + 1):
    current_subarray = A[i:i + n]
    # we now do n - 1 comparaisons to check whether the subarray is correctly ordered.
    for B_index in range(n - 1):
        if current_subarray[B[B_index]] > current_subarray[B[B_index + 1]]:
            break
    else:
        print("Subarray found:", current_subarray)

Результат:

Subarray found: [1, 5, 2]
Subarray found: [2, 4, 3]

Это работает, но мне было интересно, был ли лучше оптимизированный алгоритм (лучше, чем O(mn)) для выполнения этой задачи.

Answer 1

По крайней мере, мы могли бы намного быстрее исключать окна-кандидаты, рассматривая (двоичное) отношение соседних элементов, что могло бы позволить параллельное исследование. Звоните less than 0 и greater than 1. Тогда:

A = [1,  5,  2,  4,  3]
A'=   [0,  1,  0,  1]

B'=   [0,  1]
B = [0,  2,  1]

Очевидно, что любой кандидат должен соответствовать последовательности отношений. Также обратите внимание, что единственным типом раздела B, который может допускать перекрытие, является восходящая или нисходящая последовательность (это означает, что мы можем пропустить априори, если совпадение найдено).

Answer 2

Вместо итерации по B для сравнения рангов, вы можете использовать scipy.stats.rankdata, чтобы получить ранги напрямую:

from scipy.stats import rankdata

A = [1, 5, 2, 4, 3]
B = [0, 2, 1]

m = len(A)
n = len(B)

for i in range(m - n + 1):
    current_subarray = A[i:i + n]

    ranked_numbers = (rankdata(current_subarray).astype(int) - 1).tolist()
    if ranked_numbers == B:
        print("Subarray found:", current_subarray)

# Subarray found: [1, 5, 2]
# Subarray found: [2, 4, 3]

Примечание: rankdata() начинает ранжироваться с 1 вместо 0, поэтому вышеупомянутые минусы 1 от каждого элемента в массиве numpy.

Answer 3

Вот решение numpy, основанное на некоторой линейной алгебре.

Первое преобразование B в основу:

import numpy as np
A = [1, 5, 2, 4, 3]
B = [0, 2, 1]

b = np.eye(len(B))[B]
print(b)
#array([[1, 0, 0],
#       [0, 0, 1],
#       [0, 1, 0]])

Теперь мы можем пройти через каждый подмассив A и спроецировать его в это пространство. Если результирующий вектор отсортирован, это означает, что подрешетка следовала за ранжированием.

for i in range(0, (len(A) - len(B))+1):
    a = np.array(A[i:i+len(B)])
    if (np.diff(a.dot(b))>0).all():
        print(a)
#[1 5 2]
#[2 4 3]

Я не эксперт по пустякам, так что может быть способ оптимизировать это дальше и устранить цикл.

---

Обновление, вот более чистая версия:

def get_ranked_subarrays(A, B):
    m = len(A)
    n = len(B)
    b = np.eye(n)[B]
    a = np.array([A[i:i+n] for i in range(0, m - n+1)])
    return a[(np.diff(a.dot(b))>0).all(1)].tolist()

A = [1, 5, 2, 4, 3]
B = [0, 2, 1]
get_ranked_subarrays(A, B)
#[[1, 5, 2], [2, 4, 3]]

---

Результаты производительности:

Ваше решение очень хорошо для маленьких n, но решение numpy превосходит, когда размер A становится большим:

Вот ваш код, который я превратил в функцию, которая возвращает нужные подмассивы (вместо печати):

def get_ranked_subarrays_op(A, B):
    m = len(A)
    n = len(B)
    out = []
    for i in range(m - n + 1):
        current_subarray = A[i:i + n]
        # we now do n - 1 comparisons to check whether the subarray is correctly ordered.
        for B_index in range(n - 1):
            if current_subarray[B[B_index]] > current_subarray[B[B_index + 1]]:
                break
        else:
            out.append(current_subarray)
    return out

Временные результаты для большого случайного числа A:

array_size = 1000000
A = np.random.randint(low=0, high=10, size=array_size)
B = [0, 2, 1]

%%timeit
get_ranked_subarrays_op(A, B)
#1 loop, best of 3: 1.57 s per loop

%%timeit
get_ranked_subarrays(A, B)
#1 loop, best of 3: 890 ms per loop

Однако, если m также становится большим, ваше решение будет немного лучше из-за короткого замыкания (вероятность короткого замыкания становится большой для больших m). Вот временные результаты, которые мы позволили m быть 100.

array_size = 1000000
basis_size = 100
A = np.random.randint(low=0, high=10, size=array_size)
B = range(basis_size)
np.random.shuffle(B)

%%timeit
get_ranked_subarrays_op(A, B)
#1 loop, best of 3: 1.9 s per loop

%%timeit
get_ranked_subarrays(A, B)
#1 loop, best of 3: 2.79 s per loop

Answer 4

Вы можете перебрать A и проверить получившиеся подмассивы:

A, B = [1, 5, 2, 4, 3], [0, 2, 1]
def results(a, b):
   _l = len(b)
   for c in range(len(a)-_l+1):
     _r = a[c:c+_l]
     new_r = [_r[i] for i in b]
     if all(new_r[i] < new_r[i+1] for i in range(len(new_r)-1)):
       yield _r

print(list(results(A, B)))

Выход:

[[1, 5, 2], [2, 4, 3]]