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

Question

给定一个从 1...N 开始的整数列表，我试图找到元素的 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

我认为带有切片的简单列表理解就足够了。您可能还想使用 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] []

Answer 2

您可以使用一个函数从给定的起始数字迭代索引，默认为 1，到 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] [] []

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

Find K subsets of a list with elements 1...N while preserving the order of the elements

python

dynamic-programming

combinatorics