0

例 (または実際のユースケース) が 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..

これを行う良いPythonicの方法はありますか? 私はリスト内包表記について考えていました (そして、オブジェクトを呼び出して true と false の 2 つのオブジェクトが返されるようにオブジェクトを変更します) が、私が見た内包表記では、事前に人の数を知る必要があります。人数に関係なくやってみたいです。

編集 : これに対して実行する操作が、より大きな問題セットの一部であると仮定します。問題を解決するには、特定のセットの Person のすべての値をテストする必要があります。(つまり、これは現在NP完全に見えないことを知っています=))何かアイデアはありますか?

ありがとう！

4

3 に答える 3

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 完全とは言えません。コンピュータ サイエンスにおける NP 完全とは何ですか? を参照してください。その面の詳細については。

于 2009-02-12T01:53:54.883 に答える
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]

それはあなたがあなたの質問で述べたことの線にもっと沿っているはずです。

于 2009-02-14T02:23:09.710 に答える
1

デカルト積を使用して、人物と州のすべての可能な組み合わせを取得できます。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 のいずれかです。これには、人々と州のすべての可能な組み合わせが含まれます。

于 2009-02-12T03:06:23.430 に答える