查找元素为 1...N 的列表的 K 个子集，同时保留元素的顺序

Question

给定来自 1...NI 的整数列表，我试图找到元素的 K 个子集，同时保留元素的顺序。例如，当 N = 4 且 K = 2 时：[1] [2, 3, 4][1, 2] [3, 4][1, 2, 3] [4][1, 2, 3, 4] []将是正确的输出。到目前为止，我已经获得了第一列的可能性。但我正在努力获得正确的逻辑。    final = [['' for x in range(K)] for y in range(N)]    i = 0    for k in range(0, K):        # row tracker        i = 0        while i < N:            if k > 0:                st = len(final[i][k - 1])            else:                st = 0            for j in range(0, N):                tmp = ""                prefix = chemicals[:j + 1]                tmp = tmp.join(str(i) for i in prefix)                final[i][k] = tmp                i += 1        print同样，正确的输出将是：[1] [2, 3, 4][1, 2] [3, 4][1, 2, 3] [4][1, 2, 3, 4] []集合可以为空的地方。更新：这是 N=4, K=3 的正确输出[1] [2] [3, 4][1] [2, 3] [4][1] [2, 3, 4] [][1, 2] [3] [4][1, 2] [3, 4] [][1, 2, 3] [4] [][1, 2, 3, 4] [] []

Answer 1

您可以使用一个函数从给定的起始编号迭代索引，默认为1, to n，产生从起始编号到索引的一系列数字，并递归地将递归调用中的子集与一个更高的起始索引和少一个子集，直到起始索引大于n或k变为1，此时应产生剩余范围：

def get_subsets(n, k, s=1):

    if s > n or k == 1:

        yield [list(range(s, n + 1))] + [[] for _ in range(1, k)]

        return

    for i in range(s, n + 1):

        for subsets in get_subsets(n, k - 1, i + 1):

            yield [list(range(s, i + 1))] + subsets

以便：

for s in get_subsets(4, 2):

    print(*s)

输出：

[1] [2, 3, 4]

[1, 2] [3, 4]

[1, 2, 3] [4]

[1, 2, 3, 4] []

然后：

for s in get_subsets(4, 3):

    print(*s)

输出：

[1] [2] [3, 4]

[1] [2, 3] [4]

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

[1, 2] [3] [4]

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

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

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

Answer 2

我认为对切片进行简单的列表理解就足够了。您可能还想使用itertools.combinations：

import itertools

N = 4

K = 2

elements = list(range(1, N + 1))

final = [[elements[a:b] for a, b in zip([0] + cuts, cuts + [N])]

                        for cuts in (list(c) for c in itertools.combinations(elements, K - 1))]

for x in final:

    print(*x)

输出：

[1] [2, 3, 4]

[1, 2] [3, 4]

[1, 2, 3] [4]

[1, 2, 3, 4] []