使用递归从长度n的列表计算长度k的组合 [英] Calculating combinations of length k from a list of length n using recursion

问题描述

我需要从长度为n的列表中生成长度为k的所有组合，并且必须使用递归进行.

I need to generate all the combinations with length k from a list of length n, and I must do it using recursion.

例如:

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

我一直坚持在代码中实现此功能，因此我很乐意提供帮助. 到目前为止，这是我的代码(我遗漏了一些东西，只是不知道是什么):

I'm stuck implementing this in code, so I would be happy for some help. This is my code so far (I'm missing something just don't know what):

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

推荐答案

您可以从 4年后编辑 (2015年7月12日)

要在Python3上运行它，只需将xrange更改为range， Python3的范围是Python2的xrange..感谢 @ederollora 通知我.

To run it on Python3 just change xrange to range, Python3's range is Python2's xrange.. Thanks @ederollora to notice me.

这篇关于使用递归从长度n的列表计算长度k的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！