查找列表的所有可能子列表

Question

假设我有以下清单

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]

我想找到一段时间内所有可能的子列表，它们不包含一个特定的数字，并且不丢失数字的顺序。

例如，所有长度为6但没有12的可能子列表是：

[1,2,3,4,5,6]
[2,3,4,5,6,7]
[3,4,5,6,7,8]
[4,5,6,7,8,9]
[5,6,7,8,9,10]
[6,7,8,9,10,11]
[13,14,15,16,17,18]

问题是我想把它列在一个很大的单子里，我想用最快的方法。

使用我的方法更新：

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
newlist = []
length = 6
exclude = 12
for i in oldlist:
   if length+i>len(oldlist):
       break
   else:
       mylist.append(oldlist[i:(i+length)]
for i in newlist:
    if exclude in i:
       newlist.remove(i)

我知道这不是最好的方法，所以我需要一个更好的方法。

Answer 1

使用^{}：

import itertools
mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))
print [i for i in itertools.combinations(mylist,6) if 12 not in i and contains_sublist(mylist, list(i))]

印刷品：

[(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6, 7), (3, 4, 5, 6, 7, 8), (4, 5, 6, 7, 8, 9), (5, 6, 7, 8, 9, 10), (6, 7, 8, 9, 10, 11), (13, 14, 15, 16, 17, 18)]

Answer 2

我喜欢用可组合的小部件来构建解决方案。哈斯克尔写了几年书，你就知道了。所以我会这样做。。。

首先，这将按长度升序返回所有子列表上的迭代器，从空列表开始：

from itertools import chain, combinations

def all_sublists(l):
    return chain(*(combinations(l, i) for i in range(len(l) + 1)))

一般来说，我们不鼓励使用单字母变量名，但我认为，在高度抽象的代码中，这是一个非常合理的做法。

（顺便说一下，要省略空列表，请改用range(1, len(l) + 1)。）

然后我们可以通过添加您的标准来解决您的问题：

def filtered_sublists(input_list, length, exclude):
    return (
        l for l in all_sublists(input_list)
        if len(l) == length and exclude not in l
    )

例如：

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
length = 6
exclude = 12
newlist = filtered_sublists(old_list, length, exclude)

Answer 3

一个简单的、非优化的解决方案是

result = [sublist for sublist in 
        (lst[x:x+size] for x in range(len(lst) - size + 1))
        if item not in sublist
    ]

优化版本：

result = []
start = 0
while start < len(lst):
    try:
        end = lst.index(item, start + 1)
    except ValueError:
        end = len(lst)
    result.extend(lst[x+start:x+start+size] for x in range(end - start - size + 1))
    start = end + 1