0

我想构建一个递归函数，查找长度为 n>=k>=0 的给定列表的所有大小为“k”的子集，并返回这些子集的列表。

例如：如果输入列表是 [1,2,3,4] 并且 k = 2 那么函数将返回 [[4,3],[2,4],[2,3],[1,4], [1,3],[1,2]]

请注意，列表的不同排列被认为是同一个列表。

我认为这种递归应该有效：

return [lst[0]] + choose_sets(lst[1:],k-1)   ¬¬and¬¬   choose_sets(lst[1:],k)

choose_sets(lst,k)函数在哪里。

意义：

输入：[1,2,3,4]，k=3

调用：

[1] + [2,3,4],k=2 和 [2,3,4],k=3

等等...

谁能指导我如何“同时”调用这两个递归调用？我的“退出期限”应该是什么？

谢谢。

4

2 回答 2

2

假设您有一个 size 列表，n并且需要 size 的所有子集k。
这与以下内容基本相同：

对于列表的每个元素，创建一个没有该元素
的新列表，在新列表中，找到所有大小的子集k-1（这是递归调用），
并将删除元素添加到所有列表中。

现在......这个解决方案将有重复，例如，在你给出的例子中，你会得到 [4, 1] 和 [1, 4]。但是可以稍微改变一下，这样就不会产生重复的结果。

编辑
以处理重复 

def choose_sets(l, k):
  if k == 0:
    return [[]]
  if len(l) == 0:
    return []
  l2 = l[1:]
  subsets = choose_sets(l2, k-1)
  for s in subsets:
    s.append(l[0])
  return subsets+ choose_sets(l2, k)
于 2013-04-25T18:29:27.627 回答
0 
b = []

def abc(a,k):
    if len(a)==k:
        b.append(a)
        return b

    b.extend([a[:k-1]+[i] for i in a[k-1:]])    
    return abc(a[1:],k)


print abc([1,2,3,4,5],2)
于 2013-04-25T20:10:25.647 回答