0

我有一个项目列表，并希望生成所有可能的子集。因此，我使用了一个递归函数，其中项目编号和所有选定项目的列表作为参数。该函数以 0 作为第一个参数调用，并执行以下操作：

  • 它查看 index 参数描述的项目
  • 它选择它
  • 它使用递增的索引参数调用自身
  • 它取消选择项目
  • 它使用递增的索引参数调用自身

我需要可能的子集来优化某些东西，但由于列表会很长，我无法查看所有子集。起初我尝试使用蛮力来考虑所有子集，但这是一个幼稚的想法。现在新的计划是创建一个贪心算法，它采用第一个“有用”的选择：我想查看所有子集，直到找到一个适合我的需要并认为 python 的 yield 语句正是正确的选择。这是一些代码：

def bruteForceLeft(selected,index):
    #left is the list of which i need subsets
    #its a gobal variable. to test the code, just make sure that you have a 
    #list called left in scope
    if index==len(left):
        #print(selected)
        yield selected
    else:
        #the algorithm stores the selection in a tuple of two lists
        #that's necessary since there's a second list called right as well
        #I think you can just ignore this. Think of selected as a list that
        #contains the current selection, not a tuple that contains the current
        #selection on the right as well as the left side.
        selected[0].append(left[index])
        bruteForceLeft(selected,index+1)
        selected[0].pop()
        bruteForceLeft(selected,index+1)

#as you can see I pass a tuple of two empty lists to the function.
#only the first one is used in this piece of code
for option in bruteForceLeft( ([],[]) ,0):
    print(option)
    #check if the option is "good"
    #break

输出是：没有

起初我以为我在生成子集时出错了，但是在 if 条件下你可以看到我有一个注释打印语句。如果我取消注释此打印语句，而是注释掉 yield 语句，所有可能的选择都会被打印 - 并且 for 循环被破坏

使用 yield 语句，代码运行没有错误，但它也不做任何事情。

4

1 回答 1

4

问题是当您递归调用时bruteForceLeft，产生的值不会神奇地从封闭函数中产生。因此，您需要自己重新生成它们：

def bruteForceLeft(selected,index):
    #left is the list of which i need subsets
    if index==len(left):
        #print(selected)
        yield selected
    else:
        #the algorithm stores the selection in a tuple of two lists
        #that's necessary since there's a second list called right as well
        #I think you can just ignore this. Think of selected as a list that
        #contains the current selection, not a tuple that contains the current
        #selection on the right as well as the left side.
        selected[0].append(left[index])
        for s in bruteForceLeft(selected,index+1):
            yield s
        selected[0].pop()
        for s in bruteForceLeft(selected,index+1):
            yield s

（编辑：我实际上只是测试了这个，你的代码有错误，但我很确定不是重新生成是问题）

于 2012-11-29T21:42:32.913 回答