Давайте назначим несколько имен для описания проблемы:
m = длина последовательности массива (в вашем примере 14)
n = общее количество уникальных элементов в последовательности массива ( 3 в примере)
k = длина каждой области поиска (5 в примере)
g = количество групп, которые вы ищете (2 в примере)
Один вариант будет суммировать ваши данные в каждой области поиска размером k. В вашем примере, например так:
{B A x x C}
{A x x C x}
...
Мы создаем векторы размером n для каждого из этих разделов, первый элемент представляет внешний вид элемента первого типа, скажем A
B A x x C --> [1,1,1] (one appearance of each)
A x x C x --> [1,0,1]
и тд.
Мы можем сделать то же самое для наших групп, которые мы ищем:
{A A C} --> [2,0,1]
{A B C} --> [1,1,1]
Теперь проблема становится очевидной. Скажем, мы рассматриваем сводку области поиска [3,2,5] и сводку группы, которую мы ищем, [0,1,2], мы можем вычислить количество комбинаций, признав, что у нас было 2 варианта для второго элемента и (5x4) / (1x2) для третьего, то есть всего 20 вариантов.
Так что для краткого описания раздела, S, [s 1 , s 2 , .., s n ] и отдельная группа интересов, G, [g 1 , g 2,. ..g n ], мы можем вычислить общую сумму способов извлечения G из S (код стиля c ++, за исключением того, что "!" означает факториал):
int total_options = 1; // total ways to select G from S
for (int i = 0; i < n; ++i)
{
if(g[i] == 0)
continue; // this is an element that doesn't appear in G, so it shouldn't effect our count
if(s[i] < g[i])
return 0; // not enough elements in S for G
for (int d = 1, f = s[i]; f > max(g[i], s[i] - g[i]); --f, ++d)
total_options = total_options / d * f; // f, d are effectively factorials
// the previous loop is a more efficient version of:
// total_options *= (s[i]!) /(g[i]! * (s[i] - g[i])!);
}
return total_options;
Вы бы сделайте это для каждого раздела и каждой группы, которую вы ищете.
Сложность времени: O (g*m*(k + n)) (здесь мы должны включить k из-за факториального вычисления наихудшего случая)
Сложность пространства: O (m + g*n) (каждый раздел мы можем вычислить как go, поэтому нет необходимости хранить несколько разделов одновременно)
Затем мы можем улучшить это, осознав, что каждый Последовательный «раздел» отличается только тем, что рассматривает уходящий элемент «хвост» и входящий элемент «голова», поэтому мы должны просто рассчитать, как эти два изменяют «счетчик опций», когда мы переходим к следующему разделу. Мы сделали бы это, поддерживая предыдущее вычисление «счетчика опций», и, NF (Number Fails), количество элементов в регионе, которое было слишком низким для группы поиска. Хитрость заключается в том, чтобы поддерживать положительный «счетчик опций», который добавляется к общему итогу, только если NF равен 0. Это даст вам результаты с постоянным временем для каждого G, поскольку вы итерируете по основному массиву размера m .
Сложность времени: O (g*m + g*n)
Сложность пространства: O (g*n + m)
Этот алгоритм имеет худшую производительность, когда каждый элемент в основном массиве уникален и каждый из этих элементов появляется по крайней мере один раз в некоторых поисках (в противном случае мы можем рассматривать любые элементы, которые не отображаются ни в одном из поисков, как одинаковые, например «x» в вашем примере). Таким образом, сложности наихудшего случая могут быть упрощены до:
Сложность времени: O (g*m)
Сложность пространства: O (g*m)
Я не могу понять, как это Можно было бы получить лучшую временную сложность, но мне было бы интересно узнать, может ли какой-нибудь умный человек придумать метод с меньшей пространственной сложностью.
Если вы не знаете, о чем я говорю о том, когда речь заходит об итерации с постоянным временем с учетом только головы и хвоста, дайте мне знать, и я объясню на примере.