Получение всех возможных состояний объекта для задачи NP-Complete (?) В 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 комбинаций грустных и счастливых людей. т.е. * +1008 *

[
[ 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 для данного набора, чтобы решить нашу проблему. (то есть я знаю, что сейчас это не выглядит NP-завершенным =)) есть идеи?

Спасибо!

Answer 1

Я думаю, что это могло бы сделать это:

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 -полное. См. Что такое NP-полный в информатике? для получения дополнительной информации по этому вопросу.

Answer 2

Согласно тому, что вы заявили в своей проблеме, вы правы - вам нужно 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 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 - человек, а y - True или False. Он будет содержать все возможные пары людей и государств.