Найти K подмножеств списка с элементами 1 ... N, сохраняя при этом порядок элементов

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

Вы можете использовать функцию, которая перебирает индекс от заданного начального номера, по умолчанию от 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] [] []

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