np complete algorithm in python [solved]
Question: This question is closed.

All information about this question will be uploaded in a week. I am still
trying to figure out the full details. Still testing it as a module.

n is the number of elements and formula is a the clauses

this is an np complete algorithm.

the code tries to figure out for any permutations of n could satisfy if the
formula is correct.

    
    
    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)
    


Answer: Here is a corrected version:

    
    
    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)
    

Points to consider:

  1. Instead of introducing some complex -- and also wrong -- logic to find the conjunction and disjunction, you can use [`any`](https://docs.python.org/2/library/functions.html#any) and [`all`](https://docs.python.org/2/library/functions.html#all). That's cleaner and less prone to bugs.

  2. The natural object to loop over is `itertools.product([False, True], repeat = n)`, that is, the set `[False, True]` of possible boolean values raised to the power of `n`. In other words, the [Cartesian product](http://en.wikipedia.org/wiki/Cartesian_product) of `n` copies of `[False, True]`. [Here](https://docs.python.org/2.7/library/itertools.html#itertools.product) is the documentation for itertools.product.

  3. I introduced a bit more output to see how things are going. Here is the output I get with Python3 (Python2 adds parentheses but prints essentially the same):

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

