0

不确定该示例（也不是实际用例）是否符合 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.

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

因此，给定 PersonA、PersonB、PersonC、PersonD - 我想最终列出可能的 2**4 个悲伤和快乐人物组合的列表。IE

[
[ 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），但我看到的推导格式需要我提前知道 Persons 的数量。我想独立于人数来做到这一点。

编辑：假设我要运行的那个操作是一个更大的问题集的一部分——我们需要测试给定集的所有 Person 值以解决我们的问题。（即我知道这现在看起来不是 NP-complete =））有什么想法吗？

谢谢！

4

3 回答 3

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方法返回人本身（但这在 Python 中有点奇怪），您可以使用列表推导。用构造方法：

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

解决方案的运行时间O(n 2**n)可以通过查看循环来判断，但这并不是真正的“问题”（即带有是/否答案的问题），因此您不能真正称其为 NP-complete。请参阅什么是计算机科学中的 NP 完全？有关这方面的更多信息。

于 2009-02-12T01:53:54.883 回答
1

您可以使用笛卡尔积来获取人员和状态的所有可能组合。需要 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 是一个人，y 是 True 或 False。它将包含所有可能的人和状态配对。

于 2009-02-12T03:06:23.430 回答
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]

这应该更符合您在问题中提到的内容。

于 2009-02-14T02:23:09.710 回答