代码之家 › 专栏 › 技术社区 › rombi

从python中的连续列表中识别连续数组

continuous range list algorithm python

rombi · 技术社区 · 8 年前

python中从n个连续列表中选取多个n个连续整数,从每个列表中选取一个整数的最有效方法是什么。这里n相当大……比如说100秒左右。

L1 = [5,3,2,7,1]
L2 = [3,5,6,8,9,21,2]
L3 = [5,3,6,7,3,9]

我想从连续列表中打印出连续整数的范围,其中第一个元素从第一个列表中选取,第二个元素从第二个列表中提取,依此类推:

Candidate solution [5,6,7], [1,2,3], [7,8,9]

4 回复 | 直到 8 年前

SuperNova 8 年前

L1 = [5,3,2,7,1]
L2 = [3,5,6,8,9,21,2]
L3 = [5,3,6,7,3,9]
cons_l = []
L = [L2] + [L3] #+[L4] #+ ...+ ..... ### Add any number of list here..

j = 0
for l1 in L1:
   cons_l.append([])
   cons_l[j].append(l1)
   for l in range(0, len(L)):
      if l1+l+1 in L[l]:
         cons_l[j].append(l1+l+1)
      else:
         del cons_l[j]
         j -= 1
         break
   j += 1
print cons_l

Harper 8 年前

我会先尝试使用高效的排序算法对列表进行排序。你可以试试 Bubble Sort 但其他排序算法也可能有效。

然后,可以遍历1-n中的整数,并在字符串中查找连续的整数范围。这样,排序最多只能有n个操作,“查找”最多只能有n个操作。

这对你来说够快吗?

gboffi 8 年前

你可以使用 列表推导式 :

In [23]: ls = [[5,3,2,7,1],[3,5,6,8,9,21,2],[5,3,6,7,3,9],]

In [24]: l = len(ls)

In [25]: [list(range(s,s+l)) for s in ls[0] if all(i in l for i,l in zip(range(s+1,s+l),ls[1:]))]
Out[25]: [[5, 6, 7], [7, 8, 9], [1, 2, 3]]

它的阵风是,对于第一个列表中的每个数字,生成一个递增的数字序列,并检查每个数字是否包含在剩余列表序列中的相应列表中。

请注意 all 一旦条件不满足,就停止迭代生成器表达式,从而提高了方法的效率。

对于问题的大型实例,在理解列表之前,将所有列表转换为集合可能是值得的, ls = [set(l) for l in ls]

补遗

使用 for 循环和条件语句,请注意,在搜索序列之前,内部列表已转换为集合。

ls = [[5, 3, 2, 7, 1], [3, 5, 6, 8, 9, 21, 2], [5, 3, 6, 7, 3, 9]]
l = len(ls)
ls = [set(li) for li in ls]

candidates = []
for n in ls[0]:
    if all(i in l for i, l in zip(range(n+1, n+l), ls[1:])):
        candidates.append(list(range(n, n+l)))

MariusSiuram 8 年前

也许使用集合对于您的应用程序来说足够快了?有点蛮横,但如果我理解正确,它符合您的限制:

lists = [
  [5,3,2,7,1],
  [3,5,6,8,9,21,2],
  [5,3,6,7,3,9],
]

candidates = list()

# Without the first one
rest_of_sets = [set(l) for l in lists[1:]]

for fe in lists[0]:
    skip_partial = False
    for i, s in enumerate(rest_of_sets, 1):
        if fe + i not in s:
            skip_partial = True
            break
    if not skip_partial:
        candidates.append(range(fe, fe+len(sets)))

print candidates