python 列表项的连接组合

Question

我有一个值列表 [1,2,3,4,5,...]，我想 return 一个所有可能的 connected 组合的列表，使用列表理解、numpy 或任何有效的方法.

通过连接，我的意思是列表中的项目对应该在组合中保持它们的邻接关系（不一定是具有相邻值的整数彼此相邻，尽管这样没关系）。

明确地说，这是我想要的 returned，在列表的情况下 [1,2,3,4,5]:

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

以下是我不想要的项目类型：

[[1,2,3,5],
[1,3,4,5],
...]

我看过很多关于获得所有可能组合的帖子，但我还没有看到有人提出关于具有连通性约束的组合的问题。有什么想法吗？

Answer 1

我相信有很多方法可以做到这一点。我将建议一个可能不是更 pythonic 解决方案的简单函数。

def c_list(A):
    B = []
    for i in range(len(A)):
        for j in range(len(A) - i):
            B.append(A[j:j+i+1])
    return B

A = [ 1,2,3,4,5 ]
B = c_list(A)
print B

这个策略可以与列表理解一起使用，如果你喜欢的话：

C = [A[j:j+i+1] for i in range(len(A)) for j in range(len(A)-i)]

Answer 2

这是列表理解的一种方式：

>>> lst = [6, 7, 8, 9]
>>> [lst[i:j] for j in range(len(lst)+1) for i in range(j)]
[[6], [6, 7], [7], [6, 7, 8], [7, 8], [8], [6, 7, 8, 9], [7, 8, 9], [8, 9], [9]]

或者如果您重视订单并且我从您的示例中猜对了：

>>> [lst[i:i+leng] for leng in range(len(lst), 0, -1) for i in range(len(lst)-leng+1)]
[[6, 7, 8, 9], [6, 7, 8], [7, 8, 9], [6, 7], [7, 8], [8, 9], [6], [7], [8], [9]]

或 itertools.combinations:

>>> [lst[i:j] for i, j in combinations(range(len(lst)+1), 2)]
[[6], [6, 7], [6, 7, 8], [6, 7, 8, 9], [7], [7, 8], [7, 8, 9], [8], [8, 9], [9]]

或者甚至根本没有任何列表理解（但现在我变得愚蠢了:-)

>>> list(map(lst.__getitem__, starmap(slice, combinations(range(len(lst)+1), 2))))
[[6], [6, 7], [6, 7, 8], [6, 7, 8, 9], [7], [7, 8], [7, 8, 9], [8], [8, 9], [9]]

Answer 3

from itertools import islice
def adj(l):
    ln = len(l)
    yield l
    for n in range(ln -1, 0, -1):
        yield from (list(islice(l, i, n + i)) for i in range(ln - n % ln+1))


l = [1, 2, 3, 4, 5]
print(list(adj(l)))
[[1, 2, 3, 4, 5], [1, 2, 3, 4], [2, 3, 4, 5], [1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2], [2, 3], [3, 4], [4, 5], [1], [2], [3], [4], [5]]

您也可以一次获取一个值，而无需将所有项目存储在内存中：

def adj(l):
    ln = len(l)
    yield l
    for n in range(ln - 1, 0, -1):
        yield from (islice(l, i, n + i) for i in range(ln - n % ln+1))


l = [1, 2, 3, 4, 5]

for ele in adj(l):
    print(list(ele))

输出：

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

或者在每个切片上调用一个函数：

for ele in adj(l):
    print(sum(ele))

输出：

python 列表项的连接组合

python connected combinations of list items

python

combinations

list