0

コードに対して間違った答えが返ってきました

n は変数の数で、formula は節を含むリストです

リスト 'formula' でエンコードされた 'n' 個の変数と節を持つ SAT インスタンスを指定すると、インスタンスが満足できる場合は 'satisfiable' を返し、それ以外の場合は 'unsatisfiable' を返します。'formula' の各要素は句を表し、整数のリストです。ここで、整数 i はリテラル Xi が句に存在することを示し、整数 -i はリテラル ~Xi が句に存在することを示します。たとえば、節「X1 v ~X11 v X7」はリスト [1, -11, 7] で表されます。

import itertools
n = 4 
formula = [[1, -2, 3], [-1, 3], [-3], [2, 3]]


booleanValues = [True,False] * n

allorderings = set(itertools.permutations(booleanValues, n)) #create possible combinations of variables that can check if formula is satisfiable or not

print(allorderings)

for potential in allorderings:
    l = [] #boolean value for each variable / different combination for each iteration
    for i in potential:
        l.append(i)
    #possible = [False]*n
    aclause = []
    for clause in formula:
        something = []
        #clause is [1,2,3]
        for item in clause:
            if item > 0:
                something.append(l[item-1]) 
            else:
                item = item * -1
                x = l[item-1]
                if x == True:
                    x = False
                else:
                    x = True
                something.append(x)
        counter = 0
        cal = False
        for thingsinclause in something:
            if counter == 0:
                cal = thingsinclause
                counter = counter + 1
            else:
                cal = cal and thingsinclause
                counter = counter + 1

        aclause.append(cal)

    counter2 = 0
    formcheck = False
    for checkformula in aclause:
        if counter2 == 0:
            formcheck = checkformula
            counter2 = counter2 + 1
        else:
            formcheck = formcheck or checkformula
    print("this combination works", checkformula)
4

1 に答える 1

0

修正版は次のとおりです。

import itertools
n = 4 
formula = [[1, -2, 3], [-1, 3], [-3], [2, 3]]

allorderings = itertools.product ([False, True], repeat = n)

for potential in allorderings:
    print ("Initial values:", potential)
    allclauses = []
    for clause in formula:
        curclause = []
        for item in clause:
            x = potential[abs (item) - 1]
            curclause.append (x if item > 0 else not x)
        cal = any (curclause)
        allclauses.append (cal)
    print ("Clauses:", allclauses)
    formcheck = all (allclauses)
    print ("This combination works:", formcheck)

考慮すべき点:

  1. 論理積と論理和を見つけるために複雑な (そして間違った) ロジックを導入する代わりに、 and を使用できanyますall。これはよりクリーンで、バグが発生しにくいものです。

  2. ループする自然なオブジェクトはitertools.product([False, True], repeat = n)、つまり[False, True]可能なブール値の累乗のセットですn。つまり、のコピーのデカルト積です。itertools.productのドキュメントは次のとおりです。n[False, True]

  3. 物事がどのように進んでいるかを確認するために、もう少し出力を導入しました。これは私がPython3で得た出力です（Python2は括弧を追加しますが、基本的に同じものを出力します）：

Initial values: (False, False, False, False)
Clauses: [True, True, True, False]
This combination works: False
Initial values: (False, False, False, True)
Clauses: [True, True, True, False]
This combination works: False
Initial values: (False, False, True, False)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (False, False, True, True)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (False, True, False, False)
Clauses: [False, True, True, True]
This combination works: False
Initial values: (False, True, False, True)
Clauses: [False, True, True, True]
This combination works: False
Initial values: (False, True, True, False)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (False, True, True, True)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (True, False, False, False)
Clauses: [True, False, True, False]
This combination works: False
Initial values: (True, False, False, True)
Clauses: [True, False, True, False]
This combination works: False
Initial values: (True, False, True, False)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (True, False, True, True)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (True, True, False, False)
Clauses: [True, False, True, True]
This combination works: False
Initial values: (True, True, False, True)
Clauses: [True, False, True, True]
This combination works: False
Initial values: (True, True, True, False)
Clauses: [True, True, False, True]
This combination works: False
Initial values: (True, True, True, True)
Clauses: [True, True, False, True]
This combination works: False
于 2014-04-04T08:47:08.473 に答える