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

Не уверен, что этот пример (или фактический вариант использования) квалифицируется как NP-Complete, но мне интересно, какой способ выполнения нижеприведенного с помощью Python наиболее эффективен, предполагая, что это был доступный алгоритм.

Скажите, что у вас есть:

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..

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

РЕДАКТИРОВАТЬ: Предположим, что любая операция, которую я собирался запустить, является частью более крупного набора проблем - нам нужно проверить все значения Person для данного набора, чтобы решить нашу проблему. (т.е. я знаю, что сейчас это не выглядит NP-полным =)) какие-нибудь идеи?

Спасибо!


python iteration combinatorics
person Rizwan Kassim    schedule 12.02.2009    source источник
comment
это не имеет никакого отношения к NP-полноте ...   -  person Eli Bendersky    schedule 12.02.2009
comment
да, NPc, вероятно, был неправильным способом описать это.   -  person Rizwan Kassim    schedule 13.02.2009

Ответы (3)


arrow_upward
1
arrow_downward

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

Это должно быть больше похоже на то, что вы упомянули в своем вопросе.

person sykora    schedule 14.02.2009

arrow_upward
2
arrow_downward

Думаю, это могло бы получиться:

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

person David Z    schedule 12.02.2009
comment
Я согласен, что NPc неправильно описал это. Я не особо разбираюсь в том, что я здесь делаю ... помогите? Я предполагаю, что если бы я хотел PersonA, PersonB, я мог бы изменить строку, которая создает объект Person, чтобы вместо этого скопировать правильный корневой Person ... - person Rizwan Kassim; 13.02.2009

arrow_upward
1
arrow_downward

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

person user21714    schedule 12.02.2009