Próbuję znaleźć sposób na stworzenie algorytmu rekurencyjnego, który da wszystkie podzbiory o długości k zbioru liczb (0 -> n), ale nie mogę wysłać listy do funkcji jako argumentu.

W końcu chcę zwrócić listę list

Myślałem, żeby zacząć od końca, używając jakiegoś DP. Żadna z rzeczy, których próbowałem, nawet się do tego nie zbliżyła

Dziękuję Ci

-1
Eize 10 grudzień 2018, 02:33

1 odpowiedź

Najlepsza odpowiedź

Obsługa ostatniego elementu (n-1) w pierwszej kolejności pozwala nie przekazywać wyników pośrednich z podaną sygnaturą funkcji:

def subsets(n, k):
    if n < k or k < 0:
        return []
    if k == n:
        return [list(range(k))]
    return subsets(n-1, k) + [s+[n-1] for s in subsets(n-1, k-1)]

>>> subsets(3, 2)
[[0, 1], [0, 2], [1, 2]]
>>> subsets(4, 2)
[[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]]
>>> subsets(4, 3)
[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]
1
schwobaseggl 10 grudzień 2018, 02:52