在Python中獲取NP-Complete（？）問題的對象的所有可能狀態

不確定該示例（也不是實際用例）是否符合NP-Complete，但是我想知道最Python的Python方法下面假設這是可用的算法。在Python中獲取NP-Complete（？）問題的對象的所有可能狀態

假設你有：

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

是否有一個很好的Pythonic方法做到這一點？我在考慮列表解析（並修改對象，以便可以調用它並獲得返回的兩個對象，true和false），但是我所看到的理解格式將要求我提前知道人員數量。我希望獨立於人數這樣做。

編輯：假設無論我將要在這個上運行的操作是更大的問題集的一部分 - 我們需要測試給定集的人的所有值以解決我們的問題。（即我知道這現在看起來並不完整）=）有什麼想法？

謝謝！

來源

2009-02-12 Rizwan Kassim

這與NP完整性沒有任何關係...... – 2009-02-12 19:15:04

是啊，NPc可能是描述這個錯誤的方法。 – 2009-02-12 21:25:03

根據您在問題中陳述的內容，您是對的 - 您確實需要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-14 02:23:09 sykora

我認爲這可以做到這一點：

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。有關該方面的更多信息，請參見What is an NP-complete in computer science?。

來源

2009-02-12 01:53:54

您可以使用笛卡爾產品來獲取人員和州的所有可能組合。需要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是真或假。它將包含所有可能的人員和州的配對。

來源

2009-02-12 03:06:23 user21714

在Python中獲取NP-Complete（？）問題的對象的所有可能狀態

回答

相關問題