查找元素为 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):&nbsp; &nbsp; if s > n or k == 1:&nbsp; &nbsp; &nbsp; &nbsp; yield [list(range(s, n + 1))] + [[] for _ in range(1, k)]&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; for i in range(s, n + 1):&nbsp; &nbsp; &nbsp; &nbsp; for subsets in get_subsets(n, k - 1, i + 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield [list(range(s, i + 1))] + subsets以便：for s in get_subsets(4, 2):&nbsp; &nbsp; 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):&nbsp; &nbsp; 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 itertoolsN = 4K = 2elements = list(range(1, N + 1))final = [[elements[a:b] for a, b in zip([0] + cuts, cuts + [N])]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for cuts in (list(c) for c in itertools.combinations(elements, K - 1))]for x in final:&nbsp; &nbsp; print(*x)输出：[1] [2, 3, 4][1, 2] [3, 4][1, 2, 3] [4][1, 2, 3, 4] []