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

Question

[Дмитрий Темников]

Предположим есть список [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741] и в этом списке есть арифметическая прогрессия 1487, 4817, 8147 с шагом 3330. Какой есть оптимальный алгоритм поиска такой арифметической прогрессии? Список может быть рандомным

Answer 1

[Дмитрий Темников]

Написал такое решение. Уточнение: в моём случае заранее известно, что ищем тройки

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)

Comments

[Andrey Dugin]

Поиск по списку имеет сложность O(n), лучше использовать множество. А также некоторые эмпирические факты:

lst = set(lst)
for a, c in combinations(lst, 2):
    b, r = divmod(a + c, 2)
    if not r and b in lst:
        print(a, b, c)

Answer 2

[Роман]

к сожалению 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;
}

Answer 3

[Andrey Dugin]

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 элементов:

Comments

[longclaps]

combinations(data, 3) - это сложность О(N^3)
Можно обойтись О(N^2)

[Andrey Dugin]

longclaps, можно. Но надо исходить из постановки задачи и смысла тратить время на оптимизацию. Кстати, автор не сказал, по какому критерию алгоритм должен быть оптимальным. Мой, например, оптимален по затраченному на его написание времени - порядка 20 секунд.

[Дмитрий Темников]

Andrey Dugin, скорость вычисления, конечно же! Я просто решаю на досуге всякие задачи Эйлера. Тут надо сказать что сам массив [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741] тоже получен через permutations

for num in lst:
    combinations=itertools.permutations(str(num),4)
    lch=[int(''.join(combination)) for combination in combinations]
    lch=[num for num in lch if isPrime(num) and num>=1000]

где lst это заранее сгенерированный массив простых чисел, по идее можно далее использовать Ваше решение с combinations() и сравнить перформанс с тем решением, которое я сделал, но так как массив простых чисел не большой, то работает и так быстро

[Дмитрий Темников]

При заданной длинне массива простых чисел в 10000 и на увеличенном до 100000 выдают примерно одинаковое время. Andrey Dugin, ваше хокку сильнее, ибо написано проще. Фиг знает почему не сделал второе combinations() сразу

[Andrey Dugin]

Дмитрий Темников, по сути можно посчитать такую вещь:

import numpy as np

data = [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741]

data = np.array(data)
i = data.reshape(-1, 1, 1)
j = data.reshape(1, -1, 1)
k = data.reshape(1, 1, -1)

indices = np.where(i + j - 2 * k == 0)

for i, k, j in zip(*indices):
    if i < j < k:
        print(data[[i, j, k]])

Но поскольку здесь формируется матрица N x N x N, то можно упереться в нехватку памяти.

[Andrey Dugin]

Обновил ответ тремя вариантами разной производительности

Answer 4

[Дмитрий]

Интервал известен заранее? Если нет, то сколько чисел будут считаться прогрессией? больше 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 есть, значит последовательность найдена)

Comments

[Дмитрий Темников]

Список заранее отсортирован. Интервал прогрессии и размещение элементов заранее не известно, между элементами прогрессии может быть Х чисел, а могут идти и последовательно

[Дмитрий]

Дмитрий Темников, Тогда полагаю данный алгоритм близок к оптимальному, в питоне я не силен, на js это будет выглядеть примерно так

const findSequence = (numbers) => {
   const numbersSet = new Set(numbers)
   numbers = Array.from(numbersSet).sort((a, b) => a - b)
   
   const maxNumber = numbers[numbers.length - 1]
   let result
   
   for (let i = 0; !result && i < numbers.length - 2; i++) {
      const num1 = numbers[i]
      for (let j = i + 1; j < numbers.length - 2; j++) {
         const num2 = numbers[j]
         const diff = num2 - num1
         let nextNumber = num2 + diff
         
         if (nextNumber > maxNumber) break
         const seq = []
         
         while(numbersSet.has(nextNumber)) {
            seq.push(nextNumber)
            nextNumber += diff
         }
         
         if (seq.length) {
            result = [num1, num2, ...seq]
            break
         } 
      }
   }
   
   return result
}


const numbers = [3, 4, 7, 8, 12, 19]
document.write(findSequence(numbers))

[Роман]

Дмитрий, блин, проглядел ваш коммент и написал по сути тоже самое(

[Дмитрий]

Роман, Да ладно, автор уже сам на питоне написал =)

Answer 5

[Сергей Соколов]

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

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

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

Comments

[Andrey Dugin]

Это частный случай. в формулировке вопроса это не сработает.

[Сергей Соколов]

Andrey Dugin, ТС именно этот алгоритм и реализовал в собственном же ответе.