为NP-完全(？)获得对象的所有可能状态Python中的问题

Question

我不确定这个例子(也不是实际的用例)是否符合NP-Complete，但我想知道在假设这是可用的算法的情况下，完成下面工作的最Pythonic方式。

假设你有：

class Person:
  def __init__(self):
    self.status='unknown'
  def set(self,value):
    if value:
      self.status='happy'
    else :
      self.status='sad'
  ... blah . Maybe it's got their names or where they live or whatev.

以及一些需要一组人员的操作。(这里的关键值是这个人是快乐还是悲伤。)

因此，给定PersonA，PersonB，PersonC，PersonD -我想列出一个可能的2**4个悲伤和快乐的人的组合。即

[
[ PersonA.set(true), PersonB.set(true), PersonC.set(true), PersonD.set(true)], 
[ PersonA.set(true), PersonB.set(true), PersonC.set(true), PersonD.set(false)], 
[ PersonA.set(true), PersonB.set(true), PersonC.set(false), PersonD.set(true)], 
[ PersonA.set(true), PersonB.set(true), PersonC.set(false), PersonD.set(false)], 
etc..

有没有一种好的Pythonic式的方法来做这件事？我在考虑列表理解(并修改对象，以便您可以调用它并返回两个对象，true和false)，但我所看到的理解格式需要我提前知道Person的数量。我想独立于人数而做这件事。

编辑:假设我要运行的操作是一个更大的问题集的一部分-我们需要测试给定集的Person的所有值，以便解决我们的问题。(例如，我知道现在看起来不是NP-complete =) )有什么想法吗？

谢谢!

Answer 1

根据您在问题中所说的，您是对的--您确实需要itertools.product，但并不完全像您所说的那样。

import itertools
truth_values = itertools.product((True, False), repeat = 4)
people = (person_a, person_b, person_c, person_d)
all_people_and_states = [[person(truth) for person, truth in zip(people, combination)] for combination in truth_values]

这应该更像你在问题中提到的那样。

Answer 2

我认为这是可以做到的：

l = list()
for i in xrange(2 ** n):
    # create the list of n people
    sublist = [None] * n
    for j in xrange(n):
        sublist[j] = Person()
        sublist[j].set(i & (1 << j))
    l.append(sublist)

请注意，如果您编写Person，以便其构造函数接受该值，或者使set方法返回person本身(但这在Python语言中有点奇怪)，则可以使用列表理解。使用构造函数的方式：

l = [ [Person(i & (1 << j)) for j in xrange(n)] for i in xrange(2 ** n)]

通过查看循环可以看出，解决方案的运行时是O(n 2**n)，但它并不是真正的“问题”(即回答是/否的问题)，因此您不能真正称其为NP-complete。有关这方面的更多信息，请参阅What is an NP-complete in computer science?。

Answer 3

您可以使用笛卡尔乘积来获得人员和状态的所有可能组合。需要Python 2.6+

import itertools
people = [person_a,person_b,person_c]
states = [True,False]
all_people_and_states = itertools.product(people,states)

变量all_people_and_states包含一个元组列表(x，y)，其中x是person，y是True或False。它将包含所有可能的人员和状态配对。