Как быстро найти зависимость элементов в последовательном ряду?

Question

[xmoonlight]

Примеры.
Дан ряд: 1,2,3,4,5
-------
Начальный элемент (значение): 1
Явно видно, что каждый следующий элемент больше предыдущего на 1-цу.

Сложнее: 1,4,2,5,3,6,4
------
Начальный элемент (значение): 1
Следующий чётный больше на 3, чем предыдущий; нечётный - меньше на 2, чем предыдущий.

Вот как именно (алгоритм) можно выявлять имеющуюся зависимость (при её наличии) элементов одного произвольного ряда?

Answer 1

[Wataru]

Если зависимость может быть любая (например, числа фиббоначи) - то никак. Можно поискать последовательность на oeis.org

Если же возможна только зависимость вида +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... т.е. повторяющийся фиксированный паттерн приращений, то есть быстрое и простое решение.

Во первых, если вам дано 10 чисел, то всегда можно сказать, что есть паттерн длиной в 9 приращений.
Но можно найти кратчайший паттерн с помощью алгоритма поиска периода в строке. Буквально, по определению, нужный вам кратчайший паттерн (типа {+3, -2} для второго примера) будет периодом строки. Правда, тут не строка, а массив чисел, но это вообще никак не меняет алгоритмы. Просто у вас алфавит нестандартный.

Сначала от массива чисел перейдите к массиву приращений.

Потом можно применить жадное наивное решение - просто перебираете все возможные значения периода от 1 до n/2 и проверяете, что a[i] == a[i+str] для всех i. Как только все совпало - вы нашли период. Это решение за квадрат. Если чисел вам задано много, то можно применить префикс функцию: найдите значение префикс функции (p) для всей строки и, если ее значение больше половины длины строки, то у строки есть период n-p. Это будет линейное решение.

Еще можно применить алгоритм Дюваля. Тоже линейное решение, но более сложное в реализации и понимании.

Comments

[xmoonlight]

Спасибо большое!
Ушёл изучать.

[xmoonlight]

wataru, посмотрел...
Что решил: остановился на составлении "алфавита" (порядок следования - важен!) диагональных расстояний при сдвиге дэки.
При обнаружении дублирования значения с сохранением позиции - фиксируем паттерн. Разворачиваем структуру и получаем как раз те (из моего примера): {+3, -2}.

Можно ли проще? (я не смог проще сделать...)

[Wataru]

простите, я не понял фразу "диагональных расстояний при сдвиге дэки." Можете псевдокод привести или расписать по шагам?

Быстрое, линейное решение будет примерно такое:

// data[] - входные данные, n - их количество.
vector<int> a;
a.reserve(n-1);
for (i = 1; i < n; ++i) a.push_back(data[i] - data[i-1]);
// считаем префикс функцию для строки a.
vector<int> p(n-1);
k  = 0;
for (i = 1; i < n-1 ;++i) {
  while (k > 0 && a[k] != a[i]) k = p[k-1];
  if (a[k] == a[i]) ++k;
  p[i] = k;
}
int period = n-1;
if (p[n-2] >= (n-1)/2) period = n - 1 - p[n-2];
// ваш паттерн - a[0..period-1]

[xmoonlight]

wataru,

Можете псевдокод привести или расписать по шагам?

да, но лучше в почте продолжить...