ActiveState Code

Recipe 82346: random 3 CNF problem generator

Given the number of literals and clauses, returns a randomly generated 3-CNF sentence composed of clauses in the form of lists of tuples. The first number in the tuple is the literal; the second number is its truth value.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import random
def tcnfgen(m,k,horn=1):
    cnf = []
    def unique(l,k):
        t = random.randint(1,k)
        while(t in l):
            t = random.randint(1,k)
        return t
    r = (lambda : random.randint(0,1))
    for i in range(m):
        x = unique([],k)
        y = unique([x],k)
        z = unique([x, y],k)
        if horn:
            cnf.append([(x,1), (y,0),(z,0)])
        else:
            cnf.append([(x,r()), (y,r()),(z,r())])
    return cnf

Sign in to comment