Ответ 1

Обновление:. Первый описанный здесь алгоритм устарел вторым ответом Армин Риго, который намного проще и эффективнее. Но оба этих метода имеют один недостаток. Им нужно много часов, чтобы найти результат для миллиона целых чисел. Поэтому я попробовал еще два варианта (см. Вторую половину ответа), где диапазон входных целых чисел считается ограниченным. Такое ограничение допускает гораздо более быстрые алгоритмы. Также я попытался оптимизировать код Armin Rigo. Посмотрите результаты тестов в конце.

Вот идея алгоритма с использованием памяти O (N). Сложность времени - O (N ² log N), но может быть уменьшена до O (N ²).

Алгоритм использует следующие структуры данных:

• prev: массив индексов, указывающий на предыдущий элемент (возможно, неполной) подпоследовательности.
• hash: hashmap с ключом = разность между последовательными парами в подпоследовательности и значением = два других хэшмапа. Для этих других hashmaps: key = начальный/конечный индекс подпоследовательности, value = пара (длина подпоследовательности, конечный/начальный индекс подпоследовательности).
• pq: очередь приоритетов для всех возможных "разностных" значений для подпоследовательностей, хранящихся в prev и hash.

Алгоритм:

• Инициализировать prev с помощью индексов i-1. Обновите hash и pq, чтобы зарегистрировать все (неполные) подпоследовательности, найденные на этом шаге, и их "отличия".
• Получить (и удалить) самую маленькую "разницу" из pq. Получите соответствующую запись из hash и сканируйте одну из хэш-карт второго уровня. В это время все подпоследовательности с заданной "разностью" полны. Если хэш-карта второго уровня содержит длину подпоследовательности, которая лучше, чем найденная до сих пор, обновите лучший результат.
• В массиве prev: для каждого элемента любой последовательности, найденной на шаге 2, индекс декремента и обновление hash и, возможно, pq. При обновлении hash мы могли бы выполнить одну из следующих операций: добавить новую подпоследовательность длины 1 или вырастить некоторую существующую подпоследовательность на 1 или слить две существующие подпоследовательности.
• Удалить запись хэш-карты, найденную на шаге 2.
• Продолжайте с шага # 2, а pq не пуст.

Этот алгоритм обновляет O (N) элементов prev O (N) раз каждый. И каждому из этих обновлений может потребоваться добавить новую "разницу" в pq. Все это означает сложность времени O (N ² log N), если мы используем реализацию простой кучи для pq. Чтобы уменьшить его до O (N ²), мы могли бы использовать более сложные реализации очереди приоритетов. Некоторые из возможностей перечислены на этой странице: Приоритетные очереди.

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

И тот же код после небольшой оптимизации. Здесь поиск заканчивается, как только длина подпоследовательности, умноженная на возможную "разность" подпоследовательности, превышает диапазон списка источников.

Код Armin Rigo прост и довольно эффективен. Но в некоторых случаях он делает некоторые дополнительные вычисления, которых можно избежать. Поиск может быть прекращен, как только длина подпоследовательности, умноженная на возможную "разность" подпоследовательности, превышает диапазон списка источников:

def findLESS(A):
  Aset = set(A)
  lmax = 2
  d = 1
  minStep = 0

  while (lmax - 1) * minStep <= A[-1] - A[0]:
    minStep = A[-1] - A[0] + 1
    for j, b in enumerate(A):
      if j+d < len(A):
        a = A[j+d]
        step = a - b
        minStep = min(minStep, step)
        if a + step in Aset and b - step not in Aset:
          c = a + step
          count = 3
          while c + step in Aset:
            c += step
            count += 1
          if count > lmax:
            lmax = count
    d += 1

  return lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

Если диапазон целых чисел в исходных данных (M) мал, возможен простой алгоритм с временем O (M ²) и пространством O (M):

def findLESS(src):
  r = [False for i in range(src[-1]+1)]
  for x in src:
    r[x] = True

  d = 1
  best = 1

  while best * d < len(r):
    for s in range(d):
      l = 0

      for i in range(s, len(r), d):
        if r[i]:
          l += 1
          best = max(best, l)
        else:
          l = 0

    d += 1

  return best


print(findLESS([1, 4, 5, 7, 8, 12]))

Он похож на первый метод Armin Rigo, но он не использует никаких динамических структур данных. Я полагаю, что исходные данные не имеют дубликатов. И (чтобы код был прост), я также предполагаю, что минимальное входное значение неотрицательно и близко к нулю.

Предыдущий алгоритм может быть улучшен, если вместо массива булевых элементов мы используем структуру данных битов и побитовые операции для параллельного обработки данных. Приведенный ниже код реализует битрейт как встроенное целое число Python. Он имеет те же предположения: никакие дубликаты, минимальное входное значение неотрицательно и близко к нулю. Сложность времени - это O (M ² * log L), где L - длина оптимальной подпоследовательности, пространственная сложность O (M):

def findLESS(src):
  r = 0
  for x in src:
    r |= 1 << x

  d = 1
  best = 1

  while best * d < src[-1] + 1:
    c = best
    rr = r

    while c & (c-1):
      cc = c & -c
      rr &= rr >> (cc * d)
      c &= c-1

    while c != 1:
      c = c >> 1
      rr &= rr >> (c * d)

    rr &= rr >> d

    while rr:
      rr &= rr >> d
      best += 1

    d += 1

  return best

Ориентиры:

Входные данные (около 100000 целых чисел) генерируются следующим образом:

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

И для самых быстрых алгоритмов я также использовал следующие данные (около 1000000 целых чисел):

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

Все результаты показывают время в секундах:

Size:                         100000   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711

Ответ 2

Мы можем иметь решение O(n*m) во времени с очень небольшими потребностями в памяти, адаптируя ваши. Здесь n - количество элементов в данной входной последовательности чисел, а m - это диапазон, т.е. Наибольшее число минус наименьшее.

Вызвать A последовательность всех входных номеров (и использовать предварительно вычисленный set() для ответа в постоянное время вопрос "это число в A?" ). Вызов d шаг подпоследовательности, который мы ищем (разница между двумя номерами этой подпоследовательности). Для любого возможного значения d выполните следующее линейное сканирование по всем входным номерам: для каждого числа n из A в порядке возрастания, если число еще не было видно, посмотрите в на длину последовательности, начиная с n, с шаг d. Затем отметьте все элементы в этой последовательности, как уже было видно, так что мы не будем искать их снова, для того же d. Из-за этого сложность составляет всего O(n) для каждого значения d.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

for d in range(1, 12):
    already_seen = set()
    for a in A:
        if a not in already_seen:
            b = a
            count = 1
            while b + d in Aset:
                b += d
                count += 1
                already_seen.add(b)
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

Обновление:

• Это решение может быть достаточно хорошим, если вас интересуют только значения d, которые относительно малы; например, если получение наилучшего результата для d <= 1000 будет достаточно хорошим. Тогда сложность уменьшается до O(n*1000). Это делает алгоритм аппроксимативным, но фактически выполнимым для n=1000000. (Измеряется через 400-500 секунд с CPython, 80-90 секунд с PyPy со случайным подмножеством чисел от 0 до 10'000'000.)

• Если вы все еще хотите найти весь диапазон, и если общий случай состоит в том, что существуют длинные последовательности, заметным улучшением является остановка, как только d будет слишком большим для получения еще более длинной последовательности.

Ответ 3

ОБНОВЛЕНИЕ: я нашел статью по этой проблеме, вы можете скачать ее здесь.

Вот решение, основанное на динамическом программировании. Для этого требуется сложность времени O (n ^ 2) и сложность пространства O (n ^ 2) и не использует хеширование.

Предположим, что все числа сохраняются в массиве a в порядке возрастания, а n сохраняет свою длину. 2D-массив l[i][j] определяет длину самой длинной равноотстоящей подпоследовательности, заканчивающуюся a[i] и a[j], и l[j][k]= l[i][j] + 1, если a[j] - a[i]= a[k] - a[j] ( я < j < k).

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

Ответ 4

Алгоритм

• Основной цикл, перемещающийся по списку
• Если номер найден в списке предварительных вычислений, то он принадлежит всем последовательностям, находящимся в этом списке, пересчитывает все последовательности с count + 1
• Удалить все предварительно рассчитанные для текущего элемента
• Пересчитать новые последовательности, где первый элемент находится в диапазоне от 0 до текущего, а второй - текущий элемент обхода (фактически, не от 0 до текущего, мы можем использовать тот факт, что новый элемент не должен быть больше этого max (a), и новый список должен иметь возможность стать дольше, чем уже найдено)

Итак, для списка [1, 2, 4, 5, 7] вывод будет (это немного грязно, попробуйте сам код и посмотрите)

• индекс 0, элемент 1:
  • if 1 в precalc? Нет - ничего не делай
  • Ничего не делать
• индекс 1, элемент 2:
  • если 2 в precalc? Нет - ничего не делай
  • проверить, если 3 = 1 + (2 - 1) * 2 в нашем наборе? Нет - ничего не делай
• индекс 2, элемент 4:
  • if 4 в precalc? Нет - ничего не делать
    • проверьте, если 6= 2 + (4 - 2) * 2 в нашем наборе? Нет
    • проверьте, если 7= 1 + (4 - 1) * 2 в нашем наборе? Да - добавить новый элемент {7: {3: {'count': 2, 'start': 1}}} 7 - элемент списка, 3 - шаг.
• индекс 3, элемент 5:
  • если 5 в prealc? Нет - ничего не делать
    • не проверяйте 4, потому что 6= 4 + (5 - 4) * 2 меньше, чем вычисляемый элемент 7
    • проверьте, если 8= 2 + (5 - 2) * 2 в нашем наборе? Нет
    • check 10= 2 + (5 - 1) * 2 - больше, чем max (a) == 7
• индекс 4, элемент 7:
  • если 7 в precalc? Да - положите его в результат
    • не проверяйте 5, потому что 9= 5 + (7 - 5) * 2 больше max (a) == 7

result = (3, {'count': 3, 'start': 1}) # step 3, count 3, start 1, превратить его в последовательность

Сложность

Это не должно быть больше O (N ^ 2), и я думаю, что это меньше из-за более раннего прекращения поиска новых секвенций, я попытаюсь позже детально проанализировать

код

def add_precalc(precalc, start, step, count, res, N):
    if step == 0: return True
    if start + step * res[1]["count"] > N: return False

    x = start + step * count
    if x > N or x < 0: return False

    if precalc[x] is None: return True

    if step not in precalc[x]:
        precalc[x][step] = {"start":start, "count":count}

    return True

def work(a):
    precalc = [None] * (max(a) + 1)
    for x in a: precalc[x] = {}
    N, m = max(a), 0
    ind = {x:i for i, x in enumerate(a)}

    res = (0, {"start":0, "count":0})
    for i, x in enumerate(a):
        for el in precalc[x].iteritems():
            el[1]["count"] += 1
            if el[1]["count"] > res[1]["count"]: res = el
            add_precalc(precalc, el[1]["start"], el[0], el[1]["count"], res, N)
            t = el[1]["start"] + el[0] * el[1]["count"]
            if t in ind and ind[t] > m:
                m = ind[t]
        precalc[x] = None

        for y in a[i - m - 1::-1]:
            if not add_precalc(precalc, y, x - y, 2, res, N): break

    return [x * res[0] + res[1]["start"] for x in range(res[1]["count"])]

Ответ 5

Вот еще один ответ, работающий со временем O(n^2) и без каких-либо заметных требований к памяти, помимо того, что переключение списка в набор.

Идея довольно наивная: как и оригинальный плакат, она жадна и просто проверяет, как далеко вы можете расширить подпоследовательность из каждой пары точек, но, сначала проверяя, что мы находимся в начале подпоследовательности. Другими словами, из точек a и b вы проверяете, насколько далеко вы можете перейти на b + (b-a), b + 2*(b-a),... но только если a - (b-a) еще не находится в наборе всех точек. Если это так, то вы уже видели ту же подпоследовательность.

Хитрость заключается в том, чтобы убедить себя, что этой простой оптимизации достаточно, чтобы снизить сложность до O(n^2) от оригинала O(n^3). Это оставило для читателя упражнение:-) Время здесь конкурентоспособно с другими решениями O(n^2).

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

lmax = 2
for j, b in enumerate(A):
    for i in range(j):
        a = A[i]
        step = b - a
        if b + step in Aset and a - step not in Aset:
            c = b + step
            count = 3
            while c + step in Aset:
                c += step
                count += 1
            #print "found %d items in %d .. %d" % (count, a, c)
            if count > lmax:
                lmax = count

print lmax

Ответ 6

Теперь ваше решение O(N^3) (вы сказали O(N^2) per index). Здесь O(N^2) времени и O(N^2) решения памяти.

Идея

Если мы знаем подпоследовательность, проходящую через индексы i[0], i[1], i[2], i[3], мы не должны пытаться подпоследовательности, которая начинается с i[1] и i[2] или i[2] и i[3]

Примечание. Я отредактировал этот код, чтобы сделать его немного проще с помощью сортировки a, но он не будет работать для равных элементов. Вы можете проверить число max число равных элементов в O(N) легко

псевдокод

Я ищу только для максимальной длины, но это ничего не меняет

whereInA = {}
for i in range(n):
   whereInA[a[i]] = i; // It doesn't matter which of same elements it points to

boolean usedPairs[n][n];

for i in range(n):
    for j in range(i + 1, n):
       if usedPair[i][j]:
          continue; // do not do anything. It was in one of prev sequences.

    usedPair[i][j] = true;

    //here quite stupid solution:
    diff = a[j] - a[i];
    if diff == 0:
       continue; // we can't work with that
    lastIndex = j
    currentLen = 2
    while whereInA contains index a[lastIndex] + diff :
        nextIndex = whereInA[a[lastIndex] + diff]
        usedPair[lastIndex][nextIndex] = true
        ++currentLen
        lastIndex = nextIndex

    // you may store all indicies here
    maxLen = max(maxLen, currentLen)

Мысли об использовании памяти

O(N^2) время очень медленное для 1000000 элементов. Но если вы собираетесь запускать этот код на таком количестве элементов, самой большой проблемой будет использование памяти.
Что можно сделать, чтобы уменьшить его?

• Измените булевские массивы на битовые поля, чтобы сохранить больше логических элементов на бит.
• Сделать каждый следующий логический массив короче, потому что мы используем только usedPairs[i][j], если i < j

Немного эвристики:

• Храните только пары используемых указателей. (Конфликты с первой идеей)
• Удалить usedPairs, которые никогда не будут использовать больше (для таких i, j, которые уже были выбраны в цикле)

Ответ 7

Это мои 2 цента.

Если у вас есть список с именем input:

input = [1, 4, 5, 7, 8, 12]

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

[1, 4, 5, 7, 8, 12]
 x  3  4  6  7  11   # distance from point i to point 0
 x  x  1  3  4   8   # distance from point i to point 1
 x  x  x  2  3   7   # distance from point i to point 2
 x  x  x  x  1   5   # distance from point i to point 3
 x  x  x  x  x   4   # distance from point i to point 4

Теперь, когда у вас есть столбцы, вы можете рассмотреть элемент ввода i-th (который есть input[i]) и каждое число n в его столбце.

Цифрами, которые принадлежат к серии эквидистантных чисел, которые включают input[i], являются те, которые имеют n * j в позиции i-th своего столбца, где j - количество совпадений, уже найденных при перемещении столбцов слева направо, плюс предшественник k-th input[i], где k - индекс n в столбце input[i].

Пример: если мы рассмотрим i = 1, input[i] = 4, n = 3, тогда мы сможем идентифицировать последовательность, постигающую 4 (input[i]), 7 (поскольку она имеет 3 в позиции 1 его столбца) и 1, так как k равно 0, поэтому мы берем первый предшественник i.

Возможная реализация (извините, если код не использует те же обозначения, что и объяснение):

def build_columns(l):
    columns = {}
    for x in l[1:]:
        col = []
        for y in l[:l.index(x)]:
            col.append(x - y)
        columns[x] = col
    return columns

def algo(input, columns):
    seqs = []
    for index1, number in enumerate(input[1:]):
        index1 += 1 #first item was sliced
        for index2, distance in enumerate(columns[number]):
            seq = []
            seq.append(input[index2]) # k-th pred
            seq.append(number)
            matches = 1
            for successor in input[index1 + 1 :]:
                column = columns[successor]
                if column[index1] == distance * matches:
                    matches += 1
                    seq.append(successor)
            if (len(seq) > 2):
                seqs.append(seq)
    return seqs

Самый длинный:

print max(sequences, key=len)

Ответ 8

Перемещение массива, сохранение записи оптимального результата/с и таблицы с

(1) индекс - разность элементов в последовательности,
(2) count - количество элементов в последовательности до сих пор и
(3) последний записанный элемент.

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

Сканирование назад мы можем остановить наше сканирование, когда d больше середины диапазона массивов; или когда максимальный ток больше длины возможной последовательности, для d больше наибольшей индексированной разности. Последовательности, в которых s[j] больше, чем последний элемент в последовательности, удаляются.

Я преобразовал свой код с JavaScript в Python (мой первый код на Python):

import random
import timeit
import sys

#s = [1,4,5,7,8,12]
#s = [2, 6, 7, 10, 13, 14, 17, 18, 21, 22, 23, 25, 28, 32, 39, 40, 41, 44, 45, 46, 49, 50, 51, 52, 53, 63, 66, 67, 68, 69, 71, 72, 74, 75, 76, 79, 80, 82, 86, 95, 97, 101, 110, 111, 112, 114, 115, 120, 124, 125, 129, 131, 132, 136, 137, 138, 139, 140, 144, 145, 147, 151, 153, 157, 159, 161, 163, 165, 169, 172, 173, 175, 178, 179, 182, 185, 186, 188, 195]
#s = [0, 6, 7, 10, 11, 12, 16, 18, 19]

m = [random.randint(1,40000) for r in xrange(20000)]
s = list(set(m))
s.sort()

lenS = len(s)
halfRange = (s[lenS-1] - s[0]) // 2

while s[lenS-1] - s[lenS-2] > halfRange:
    s.pop()
    lenS -= 1
    halfRange = (s[lenS-1] - s[0]) // 2

while s[1] - s[0] > halfRange:
    s.pop(0)
    lenS -=1
    halfRange = (s[lenS-1] - s[0]) // 2

n = lenS

largest = (s[n-1] - s[0]) // 2
#largest = 1000 #set the maximum size of d searched

maxS = s[n-1]
maxD = 0
maxSeq = 0
hCount = [None]*(largest + 1)
hLast = [None]*(largest + 1)
best = {}

start = timeit.default_timer()

for i in range(1,n):

    sys.stdout.write(repr(i)+"\r")

    for j in range(i-1,-1,-1):
        d = s[i] - s[j]
        numLeft = n - i
        if d != 0:
            maxPossible = (maxS - s[i]) // d + 2
        else:
            maxPossible = numLeft + 2
        ok = numLeft + 2 > maxSeq and maxPossible > maxSeq

        if d > largest or (d > maxD and not ok):
            break

        if hLast[d] != None:
            found = False
            for k in range (len(hLast[d])-1,-1,-1):
                tmpLast = hLast[d][k]
                if tmpLast == j:
                    found = True
                    hLast[d][k] = i
                    hCount[d][k] += 1
                    tmpCount = hCount[d][k]
                    if tmpCount > maxSeq:
                        maxSeq = tmpCount
                        best = {'len': tmpCount, 'd': d, 'last': i}
                elif s[tmpLast] < s[j]:
                    del hLast[d][k]
                    del hCount[d][k]
            if not found and ok:
                hLast[d].append(i)
                hCount[d].append(2)
        elif ok:
            if d > maxD: 
                maxD = d
            hLast[d] = [i]
            hCount[d] = [2]


end = timeit.default_timer()
seconds = (end - start)

#print (hCount)
#print (hLast)
print(best)
print(seconds)

Ответ 9

Это частный случай для более общей проблемы, описанной здесь: Откройте длинные шаблоны, где K = 1 и исправлено. Там показано, что его можно решить в O (N ^ 2). Запустив мою реализацию алгоритма C, предложенного там, требуется 3 секунды, чтобы найти решение для N = 20000 и M = 28000 на моей 32-битной машине.

Ответ 10

Жадный метод
1. Создается только одна последовательность решений.
2. Создано много решений. Динамическое программирование 1. Это не гарантирует оптимальное решение.
2. Это определенно дает оптимальное решение.