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

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)

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

- Tasos

---

http://docs.python.org/2/library/itertools.html#itertools.combinations - zch

为什么不先从输入中删除12，而不是试图弄清楚哪些组合包括或排除它呢？ - Karl Knechtel

Answer 1

使用 itertools.combinations ：

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

- TerryA

---

这是一个不错的答案，但将其转换为字符串会使列表中任何没有__str__或__repr__方法的对象无法使用。 - StoryTeller - Unslander Monica

我不想丢失数字的顺序，我希望它是一个连续的子列表。例如 (1, 2, 13, 14, 15, 16) 不符合我的要求。我将我的方法添加到评论中，但我认为这不是最好的方式。 - Tasos

我认为生成大量未使用的组合（全部包含12）并过滤它们不是最快的方法。相反，应该有一个没有12的列表副本被处理，或者从一个少一个元素的列表到所需列表的某种映射（例如通过将所有结果数字>= 12加1）。 - Michael Butscher

@StoryTeller 不好意思，我刚从https://dev59.com/bXA75IYBdhLWcg3waIMJ获取的。现在我有的（也来自这个问题）应该可以工作 :)。 - TerryA

Answer 2

一个简单但未经优化的解决方案是：

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

- georg

---

你能优化它多少呢 :) 在我看来，这里确实需要一个“滑动窗口”解决方案。+1。 - StoryTeller - Unslander Monica

这里的“item”是什么？第二个版本对我无效：“NameError：name 'item' is not defined”。 - milcak

第一个版本也不起作用，因为“item”未定义。 - Dennis Golomazov

这里的 size 在两个解决方案中是什么意思？它也没有被定义。 - Pabitra Pati

Answer 3

我能想到的最简单的方法是从列表中删除被排除的数字，然后使用itertools.combinations()生成所需的子列表，这样做还有一个优点，它可以迭代地产生子列表。

from  itertools import combinations

def combos_with_exclusion(lst, exclude, length):
    for combo in combinations((e for e in lst if e != exclude), length):
        yield list(combo)

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

for sublist in combos_with_exclusion(mylist, 12, 6):
    print sublist

输出：

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

- martineau

Answer 4

我喜欢使用小的可组合部件来构建解决方案。写了几年Haskell之后，你就会这样做。

所以我会像这样做...

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

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)

- gimboland

Answer 5

我尝试使用递归创建所有可能的列表。深度参数表示每个列表从中删除项的数量。这不是滑动窗口。

代码:

def sublists(input, depth):
    output= []
    if depth > 0:
        for i in range(0, len(input)):
            sub= input[0:i] + input[i+1:]
            output += [sub]
            output.extend(sublists(sub, depth-1))
    return output

示例（在python3中交互式输入）：

sublists([1,2,3,4],1)

[[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]]

sublists([1,2,3,4],2)

[[2, 3, 4], [3, 4], [2, 4], [2, 3], [1, 3, 4], [3, 4], [1, 4], [1, 3], [1, 2, 4], [2, 4], [1, 4], [1, 2], [1, 2, 3], [2, 3], [1, 3], [1, 2]]

sublists([1,2,3,4],3)

[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3], [2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3], [1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2], [1], [1, 2, 3], [2, 3], [3], [2], [1, 3], [3], [1], [1, 2], [2], [1]]

一些边缘情况：

sublists([1,2,3,4],100)

[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3], [2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3], [1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2], [1], [1, 2, 3], [2, 3], [3], [2], [1, 3], [3], [1], [1, 2], [2], [1]]

sublists([], 1)

[]

注意：输出的列表中包含重复项。

- Megatron

Answer 6

我有一个答案，但我认为它不是最好的：

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
result = []
def sub_list(lst):
    if len(lst) <= 1:
        result.append(tuple(lst))
        return
    else:
        result.append(tuple(lst))
    for i in lst:
        new_lst = lst[:]
        new_lst.remove(i)
        sub_list(new_lst)
sub_list(oldlist)
newlist = set(result)    # because it have very very very many the same
                         # sublist so we need use set to remove these also 
                         # use tuple above is also the reason 
print newlist

这种方法可以得到结果，但是由于会有很多相同的子列表，所以需要大量的内存和时间。我认为这不是一个好的方式。

- Laobe