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.
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
|
Tags: algorithms