最长的等距子序列

我有一百万个整数排列顺序，我想find连续对之间的差异相等的最长的子序列。 例如

1, 4, 5, 7, 8, 12 

有一个子序列

  4, 8, 12 

我的天真的方法是贪婪，只是检查你可以从每个点扩展一个子序列多远。 这似乎每点O(n²)时间。

有没有更快的方法来解决这个问题？

更新。 我会尽快testing答案中给出的代码（谢谢）。 但是很明显，使用n ^ 2内存将不起作用。 到目前为止，没有任何以input结束的代码为[random.randint(0,100000) for r in xrange(200000)] 。

计时。 我在32位系统上testing了以下input数据。

 a= [random.randint(0,10000) for r in xrange(20000)] a.sort() 

• ZelluX的dynamic编程方法使用1.6G的RAM，耗时2分14秒。 随着pypy只需要9秒！ 但是，它在大input上出现内存错误。
• Armin的O（nd）时间方法花了9秒的时间，但只有20MB的RAM。 当然如果范围要大得多，情况会更糟。 低内存使用意味着我也可以在xrange（200000）中使用= [random.randint（0,100000）]来testing它，但是在我用pypy给它的几分钟内它没有完成。

为了能够testingKluev的方法我reran与

 a= [random.randint(0,40000) for r in xrange(28000)] a = list(set(a)) a.sort() 

把一个长度约为20000的清单。 所有的时间与pypy

• ZelluX，9秒
• Kluev，20秒
• 阿明，52秒

看来，如果ZelluX方法可以做成线性空间，那将是明显的赢家。

Answer 1

更新：这里描述的第一个algorithm已经被Armin Rigo的第二个答案废弃了，这个答案更简单，更高效。 但是这两种方法都有一个缺点。 他们需要许多小时才能find一百万个整数的结果。 所以我尝试了另外两种变体（参见本答案的后半部分），其中input整数的范围被认为是有限的。 这种限制允许更快的algorithm。 此外，我试图优化Armin Rigo的代码。 在最后看到我的基准testing结果。

---

这里是使用O（N）存储器的algorithm的一个想法。 时间复杂度是O（N ² log N），但可能会减less到O（N ² ）。

algorithm使用以下数据结构：

1. prev ：指向前一个元素（可能不完整）子序列的索引数组。
2. hash ：哈希映射关键字=连续对之间的子序列和值=两个其他hashmaps。 对于这些其他hashmaps：key =子序列的开始/结束索引，value =（子序列长度，子序列的结束/开始索引）对。
3. pq ：优先级队列，用于存储在prev和hash序列的所有可能的“差异”值。

algorithm：

1. 用索引i-1初始化prev 。 更新hash和pq来注册在这个步骤中find的所有（不完整的）子序列和它们的“差异”。
2. 从pq获取（并移除）最小的“差异”。 从hash获取相应的logging并扫描二级哈希映射之一。 此时所有具有“差异”的子序列都是完整的。 如果二级哈希映射包含的子序列长度比迄今为止发现的更好，则更新最佳结果。
3. 在数组prev ：对于在步骤2中find的任何序列的每个元素，递减索引和更新hash以及可能的pq 。 在更新hash ，我们可以执行以下操作之一：添加长度为1的新子序列，或者将某个现有子序列增加1，或合并两个现有的子序列。
4. 删除第2步中find的哈希映射logging。
5. 当pq不为空时，从步骤＃2继续。

该algorithm更新每个O（N）次的O（N）元素。 而且这些更新中的每一个都可能需要为pq添加一个新的“差异”。 所有这些都意味着O（N ² log N）的时间复杂度，如果我们使用pq简单堆实现。 为了减less到O（N ² ），我们可以使用更高级的优先级队列实现。 本页列出了一些可能性： 优先级队列 。

在Ideone上查看相应的Python代码。 此代码不允许列表中的重复元素。 有可能解决这个问题，但是无论如何删除重复（并且find超出重复的最长的子序列）将是一个很好的优化。

和相同的代码经过一些优化 。 在这里，只要子序列长度乘以可能的子序列“差值”超过了源列表范围，search就终止。

---

Armin Rigo的代码简单而高效。 但是在某些情况下，它可以避免一些额外的计算。 只要子序列长度乘以可能的子序列“差值”超过源列表范围，search就可以终止：

 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）空间简单的algorithm：

 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的第一种方法，但不使用任何dynamic数据结构。 我想源数据没有重复。 而且（为了保持代码简单），我还假设最小input值是非负的，接近零。

---

以前的algorithm可能会改进，如果不是布尔数组我们使用bitset数据结构和按位运算来并行处理数据。 下面显示的代码将bitset实现为内置的Python整数。 它有相同的假设：没有重复，最小input值是非负的，接近零。 时间复杂度为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 

---

基准：

input数据（大约100000个整数）是这样产生的：

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

而对于最快的algorithm，我也使用了以下数据（大约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 

Answer 2

我们可以通过调整你的解决scheme，只需很less的内存就可以解决O(n*m) 。 这里n是给定input数字序列中的项目数量， m是范围，即最高的数字减去最低的数字。

调用所有input数字的序列（并使用一个预先计算好的set()在不变的时间回答问题“这个数字在A？”）。 调用我们正在寻找的子序列的步骤 （这个子序列的两个数字之间的差异）。 对于d的每个可能的值，对所有input数字进行以下线性扫描：对于来自A的每个数字n按递增顺序，如果该数字尚未被看到，则在A中向前看从n开始的具有步骤d。 然后按照已经看到的顺序标记所有的项目，这样我们可以避免再次search它们。 正因为如此，d的每个值的复杂度都是O(n) 。

 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' 

更新：

• 这个解决scheme可能是足够好的，如果你只对d的值比较小， 例如，如果得到d <= 1000的最佳结果就足够了。 然后复杂度降到O(n*1000) 。 这使得该algorithm是近似的，但实际上可运行n=1000000 。 （用CPython在400-500秒内测量，用PyPy测量为80-90秒，随机子数在0-10'000'000之间）。

• 如果你还想search整个范围，如果常见的情况是存在长序列，那么显着的改进就是一旦d太大而停止，甚至更长的序列被发现。

Answer 3

更新：我发现这个问题的文件，你可以在这里下载。

这是一个基于dynamic编程的解决scheme。 它需要O（n ^ 2）时间复杂度和O（n ^ 2）空间复杂度，而不使用散列。

我们假设所有的数字按照升序存储在数组a中， n保存它的长度。 2Darraysl[i][j]定义了以a[i]和a[j]结束的最长等距子序列的长度，如果a[j] l[i][j] a[j] – a[i] = a[k] – a[j] （i <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 

Answer 4

algorithm

• 主循环遍历列表
• 如果在预计算列表中find数字，则它属于该列表中的所有序列，重新计算count + 1的所有序列
• 删除所有预先计算的当前元素
• 重新计算新的序列，其中第一个元素的范围从0到当前，第二个是当前的遍历元素（实际上，不是从0到当前，我们可以使用新元素不应该超过max（a）和new名单应该有可能变得更长已经find了一个）

所以对于列表[1, 2, 4, 5, 7]输出将是（这是一个小混乱，尝试编码自己，看看）

• 索引0 ，元素1 ：
  • 如果在precalc？ 不 – 什么也不做
  • 没做什么
• 索引1 ，元素2 ：
  • 如果2在precalc？ 不 – 什么也不做
  • 检查3 = 1 +（ 2 – 1 ）* 2在我们的集合？ 不 – 什么也不做
• 索引2 ，元素4 ：
  • 如果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在我们的集合？ 没有
    • 检查10 = 2 +（ 5 – 1 ）* 2 – 超过最大（a）== 7
• 索引4 ，元素7 ：
  • 如果7在precalc？ 是的 – 把它结果
    • 不检查5因为9 = 5 +（ 7 – 5 ）* 2大于max（a）== 7

结果=（3，{'count'：3，'start'：1}）＃步骤3，计数3，开始1，将其变成序列

复杂

它不应该超过O（N ^ 2），我认为这是因为提前终止search新的顺序，我会尽力提供详细的分析

码

 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"])] 

Answer 5

下面是另外一个答案，在O(n^2)时间内工作，除了把列表变成一个集合之外，没有任何明显的内存要求。

这个想法是相当天真的：就像原来的海报，它是贪婪的，只是检查你可以从每一对点扩展一个子序列多远 – 但是，首先检查我们是在一个子序列的开始 。 换句话说，从a和b点你可以看到你能扩展到b + (ba) ， b + 2*(ba) ，…但是只有当a - (ba)不在所有的集合点。 如果是，那么你已经看到了相同的子序列。

诀窍是说服自己，这个简单的优化足以将复杂度从原来的O(n^3)降低到O(n^2) O(n^3) 。 这留给了读者:-)这里的时间与其他的O(n^2)解决scheme是相互竞争的。

 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 

Answer 6

你现在的解决scheme是O(N^3) （你说O(N^2) per index ）。 这里是O(N^2)的时间和O(N^2)的内存解决scheme。

理念

如果我们知道通过索引i[0] ， i[1] ， i[2] ， i[3]序列，我们不应该尝试以i[1]和i[2]或i[2]和i[3]

注意我编辑的代码，使它更容易使用asorting，但它不会工作的相等元素。 你可以容易地检查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)时间对于100万个元素来说非常缓慢。 但是如果你打算在这么多的元素上运行这个代码，最大的问题就是内存的使用。
可以做些什么来减less呢？

• 将布尔数组更改为位域以存储每位更多的布尔值。
• 使每个下一个布尔数组更短，因为如果i < j只使用usedPairs[i][j]

很less的启发式：

• 只存储使用的指示对。 （与第一个想法冲突）
• 移除永远不会用得更多的usedPair（对于已经在循环中select的i ， j ）

Answer 7

这是我的2美分。

如果你有一个名为input的列表：

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

你可以build立一个数据结构，对于每一个点（不包括第一个点），都会告诉你这个点与其前任有什么不同：

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

现在你已经有了列，你可以考虑第i-thinput项（它是input[i] ）和列中的每个数字n 。

属于包含input[i]的一系列等距数字的数字是那些在其列i-th位置具有n * j i-th的数字，其中j是当从左向右移动列时已经find的匹配数目加上input[i] k-th前辈，其中k是input[i]列中的n的索引。

例如：如果我们考虑i = 1 ， input[i] = 4 ， n = 3 ，那么我们可以识别一个包含4 （ input[i] ）， 7的序列（因为它的列的位置1有3 ）和1 ，因为k是0，所以我们把我的第一个前任。

可能的实现（抱歉，如果代码没有使用与解释相同的符号）：

 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) 

Answer 8

遍历数组，logging最优结果和一张表

（1）索引 – 序列中的元素差异，
（2）计数 – 到目前为止序列中的元素数目，以及
（3）最后logging的元素。

对于每个数组元素来看看每个前面的数组元素的差异; 如果该元素是表中索引序列中的最后一个，请在表中调整该序列，并在适用的情况下更新最佳序列，否则开始一个新序列，除非当前max大于可能序列的长度。

向后扫描，当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) 

Answer 9

对于这里描述的更一般的问题，这是一个特例： 发现 K = 1且固定的长模式 。 可以用O（N ^ 2）来解决。 Runnig提出了我的Calgorithm的实现方法，在我的32位机器上findN = 20000和M = 28000的解决scheme需要3秒。

Answer 10

贪婪的方法
1。仅产生一个决定序列。
2.生成许多决定。 dynamic编程1.不保证始终提供最佳解决scheme。
这绝对是一个最佳的解决scheme。