Z3 中的所有不同约束除外

Question

有没有办法在 Z3 中只用 O(n) 条语句生成一个全不同的约束？我知道 XCSP3 提供这个。

这目前可以像这样用 O(n^2) 语句来完成：

for i in range(len(G) - 1):
    s.add( [ Or(G[i] == 0, G[i] != G[j]) for j in range(i + 1, len(G)) ] )

如果重要的话，我有兴趣比较位向量。

Answer 1

Z3 确实带有一个 Distinct 谓词来确保所有元素都不同，但据我所知，没有内置的 distinct-except.

为了对这种约束进行编码，我将使用一个数组来跟踪插入元素的基数。像这样：

from z3 import *

def distinct_except(G, ignored):
   if len(G) < 2:
       return BoolSort().cast(True)

   A = K(G[0].sort(), 0);
   for i in range(len(G)):
       A = Store(A, G[i], If(G[i] == ignored, 0, 1 + Select(A, G[i])))

   res = True
   for i in range(len(G)):
       res = And(res, Select(A, G[i]) <= 1)

   return res

我们只需将元素插入数组，如果元素未被忽略，则计数增加 1，否则放入 0。这避免了昂贵的 if-then-else 节点，因为数组是线性构建的。然后我们再次遍历列表并确保我们没有存储任何大于 1 的东西。

这将使表达式 res 和 A 的大小保持线性，z3 应该能够相当有效地处理它。如果您有其他发现，我想听听。

这里有一些测试可以看到它的实际效果：

# Test: Create four variables, assert they are distinct in the above sense
a, b, c, d = BitVecs('a b c d', 32)
s = Solver()
s.add(distinct_except([a, b, c, d], 0))

# Clearly sat:
print s.check()
print s.model()

# Add a constraint that a and b are equal
# Still SAT, because we can make a and b 0
s.add(a == b)
print s.check()
print s.model()

# Force a to be non-zero
s.add(a != 0)

# Now we have unsat:
print s.check()

这会打印：

sat
[b = 1024, a = 16, c = 1, d = 536870912]
sat
[c = 33554432, a = 0, d = 32768, b = 0]
unsat

请注意，您始终可以使用 print s.sexpr() 查看您构建的表达式，然后再调用 s.check() 查看它们如何随着输入列表变大而增长。

Z3 中的所有不同约束除外

All-Different-Except Constraint in Z3

big-o

z3

z3py

bitvector