Получение всех возможных состояний объекта для задачи NP-Complete (?) В Python

Question

Не уверен, что пример (или фактический usecase) квалифицируется как 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.. 

Есть ли хороший питонический способ сделать это? Я думал о понимании списков (и модификации объекта, чтобы вы могли его вызвать и получить два объекта, true и false), но форматы понимания, которые я видел, потребуют от меня знать количество Первых заранее. Я бы хотел сделать это независимо от количества людей.

EDIT: Предположим, что любая операция, которую я собираюсь запустить на этом, является частью более сложного набора проблем - нам нужно проверить все значения Person для данного набора, чтобы решить нашу проблему. (т. е. я знаю, что это не выглядит NP-полным прямо сейчас =)) любые идеи?

Спасибо!

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 вернулся сам человек (но это немного странно в Python), вы можете использовать понимание списка. С конструктором пути:

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

Среда решения является O(n 2**n), как вы можете сказать, глядя на петлях, но это на самом деле не «проблема» (то есть вопрос с да/нет ответа), так что вы не может называть его NP-полным. См. 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 содержит список кортежей (х, у), где х человек и у является истинным или ложным. Он будет содержать все возможные пары людей и государств.