exibite777
@exibite777
Ведущий системный аналитик

Как найти арифметическую прогрессию в списке?

Предположим есть список [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741] и в этом списке есть арифметическая прогрессия 1487, 4817, 8147 с шагом 3330. Какой есть оптимальный алгоритм поиска такой арифметической прогрессии? Список может быть рандомным
  • Вопрос задан
  • 5091 просмотр
Решения вопроса 3
exibite777
@exibite777 Автор вопроса
Ведущий системный аналитик
Написал такое решение. Уточнение: в моём случае заранее известно, что ищем тройки
lst=[1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741]
    for i in range(len(lst)):
        for j in range(i+1,len(lst)):
            diff=lst[j]-lst[i]
            if lst[j]+diff in lst:
                print(lst[i],lst[j],lst[j]+diff)
Ответ написан
lastuniverse
@lastuniverse
Всегда вокруг да около IT тем
к сожалению python не мой рабочий инструмент, поэтому сделал реализацию на js. Старался не использовать "особые фишки" языка, чтобы получить более универсальный код (с точки зрения переносимости на другие ЯП). Думаю вы без проблем сможете переписать его на python.

var arr1 = [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741];
var res1 = search(arr1);
console.log(res1); 
// найдена 1 прогрессия. выведет:
// [ 
//   [ 1487, 4817, 8147 ] 
// ]



var arr2 = [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741, 10001];
var res2 = search(arr2);
console.log(res2); 
// найдено 2 прогрессии. выведет:
// [ 
//   [ 1487, 4817, 8147 ],
//   [ 7481, 8741, 10001 ]
// ]






function search(a){
	// создадим массив, в который будем заносить данные о найденых прогрессиях
	var result = [];

	// проверяем в цикле все числа
	for(var start=0; start<a.length; start++){
		for(var i=start+1; i<a.length; i++){

			// вычисляем предпологаемый шаг прогрессии
			var step = a[i]-a[start]; 

			// и проверяем его.

			// создаем массив, в который складываем 
			// числа предполагаемой прогрессии
			var list = [ a[start], a[i] ]; 

			// смотрим в цикле следующие числа
			for(var j = i+1; j< a.length; j++){
				// если следующее число - шаг прогрессии равно
				// последнему занесенному в массив list
				// то добавляем его в массив list
				if( a[j]-step == list[list.length-1]){
					list.push(a[j]);
				}
			}

			// если в массиве 3 элемента или более, то считаем что
			// еще одна прогрессия найдена и запоминаем ее в
			// массиве с результатами
			if( list.length>2){
				result.push(list);
			}

			console.log(start, i, step, list)
		}
	}

	// возвращаем массив результатов
	return result;
}
Ответ написан
Комментировать
adugin
@adugin Куратор тега Python
import numpy as np
from collections import deque
from itertools import combinations

# data = np.array([1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741])

np.random.seed(42)
data = np.random.randint(0, 100000, 1000)
data.sort()

# Интуитивный подход (baseline), O(n^3)
def find_evenly_spaced_v1(data):
    for a, b, c in combinations(data, 3):
        if b - a == c - b:
            yield a, b, c
            
# Эмпирическая оптимизация, O(n^2)
def find_evenly_spaced_v2(data):
    dataset = set(data)
    for a, c in combinations(data, 2):
        b, mod = divmod(a + c, 2)
        if (mod == 0) and (b in dataset):
            yield a, b, c

# Векторный вариант
def find_evenly_spaced_v3(data):
    grid = data.reshape(-1, 1) + data.reshape(1, -1)
    divs, mods = np.divmod(grid, 2)
    mask = np.tri(*grid.shape, -1, dtype='bool') & np.isin(divs, data) & ~ mods.astype('bool')
    for c, a in zip(*np.where(mask)):
        b = divs[a, c]
        a, c = data[[a, c]]
        yield a, b, c

Измерения скорости для 1000 элементов:

5d95912c852ea517827440.png
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@dimoff66
Кратко о себе: Я есть
Интервал известен заранее? Если нет, то сколько чисел будут считаться прогрессией? больше 2?

Взять уникальные значения, отсортировать по возрастанию, запихнуть в хэш и далее искать, начиная с меньшего, смотреть разницу с каждым бОльшим числом и проверять наличие большего числа * 2 минус меньшее число.

Например для последовательности 8, 4, 12, 7, 3
Получаем отсортированный массив 3, 4, 7, 8, 12
Для 3ки ничего не находим
Для 4ки проверяем 7: 7 * 2 - 4 = 10 (10 не найдено)
Для 4ки проверяем 8: 8 * 2 - 4 = 12 (12 есть, значит последовательность найдена)
Ответ написан
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Для первого числа построить массив разниц с каждым из остальных, что правее.

Для второго массив разниц с теми, что правее.
И так для всех.

Затем в массивах этих разниц найти хотя бы два одинаковых.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы