alcular combinações de comprimento k de uma lista de comprimento n usando recursão

Question

Dec 30, 2011, 08:16 PM

alcular combinações de comprimento k de uma lista de comprimento n usando recursão

Preciso gerar todas as combinações com comprimentok de uma lista de comprimenton, e devo fazê-lo usando recursã

Por exemplo

INPUT:  choose_sets([1,2,3,4],3)
OUTPUT: [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

INPUT:  choose_sets([1,2,3,4],2)
OUTPUT: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Estou preso ao implementar isso no código, então ficaria feliz em receber alguma ajuda. Este é o meu código até agora (estou faltando algo, mas não sei o que):

def choose_sets(lst,k):

    if k == len(lst):
        return lst
    if k == 0:
        return []
    if k > len(lst):
        return []

    sets=[]
    sub_lst=lst[:]
    sub_lst.remove(sub_lst[0])

    a= choose_sets(sub_lst,k-1)
    for i in a:
        i.append(lst[0])
    sets.append(a)

    b= choose_sets(sub_lst,k)
    sets.append(b)


    return sets