Ottenere tutti i possibili stati di un oggetto per un NP-completo (?) Problema in Python

Question

Non sono sicuro che l'esempio (né il caso d'uso reale) si qualifica come NP-completo, ma mi chiedo il modo più Pythonic di fare il seguito ammesso che questo era l'algoritmo a disposizione.

Diciamo che avete:

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.

e qualche operazione che richiede un gruppo di persone. (Il valore della chiave è qui se la persona è felice o triste.)

Quindi, dato Persona, PersonB, PersonC, PersonD - mi piacerebbe finire un elenco dei possibili 2 ** 4 combinazioni delle persone tristi e felici. cioè.

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

C'è un buon modo Pythonic di fare questo? Stavo pensando di list comprehension (e modificare l'oggetto in modo che si potrebbe chiamare e ottenere tornati due oggetti, vere e false), ma i formati di comprensione che ho visto mi avrebbe bisogno di conoscere il numero delle persone in anticipo. Mi piacerebbe fare questo indipendentemente dal numero di persone.

EDIT: Si supponga che qualunque cosa ciò operazione che stavo andando a correre su questo è parte di un problema più ampio set - abbiamo bisogno di testare tutti i valori di persona per un determinato insieme al fine di risolvere il nostro problema. (Vale a dire So che questo non sembra NP-completo adesso =)) tutte le idee?

Grazie!

Answer 1

Secondo quello che hai indicato nel tuo problema, hai ragione - avete bisogno di itertools.product, ma non esattamente il modo in cui hai dichiarato

.

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]

Questo dovrebbe essere più lungo le linee di quello che lei ha citato nella sua interrogazione.

Answer 2

Credo che questo potrebbe farlo:

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)

Si noti che se hai scritto Person in modo che il suo costruttore ha accettato il valore, o tali che il metodo set restituito alla persona in sé (ma questo è un po 'strano in Python), è possibile utilizzare un elenco di comprensione. Con il modo in cui il costruttore:

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

Il tempo di esecuzione della soluzione è O(n 2**n) come si può dire, cercando in loop, ma non è davvero un "problema" (cioè una domanda con una risposta sì / no) quindi non si può davvero chiamare NP-completo . Vedere Cos'è un NP-completo in informatica? Per ulteriori informazioni su tale anteriore.

Answer 3

È possibile utilizzare un prodotto cartesiano per ottenere tutte le possibili combinazioni di persone e gli stati. Richiede Python 2.6 +

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

La variabile all_people_and_states contiene una lista di tuple (x, y), dove x è una persona ey è True o False. Conterrà tutti i possibili abbinamenti di persone e gli stati.