# encoding: -utf8-
# Note: it works with Python >= 2.6
###
### Pierre Hyvernat
###
### proof of concept, quick implementation of the algorithm from "Some
### Properties of Inclusions of Multisets and Contractive Boolean
### Functions"
### Go to http://lama.univ-savoie.fr/~hyvernat/ for the paper.
###
###
###
### It uses Python built-in "set" and "dictionary" (for the function F) types.
### Because tuples aren't mutable and lists aren't hashable, we need to
### convert between the two.
###
### Boolean tuples are represented by n-tuples of integers 0 / 1.
###
def sup(u,v):
"""Computes the sup of two boolean tuples.
Complexity: O(n)
"""
n = len(u)
assert len(v) == n
w = [0]*n
for i in range(n):
w[i] = u[i] or v[i]
return tuple(w)
def chi(a,Z):
"""Computes the "characteristic function" χ(a) of "a" wrt the n-tuple of
sets "Z".
If z is the maximal cardinality of elements of Z, complexity: O(n log(z).
"""
n = len(Z)
c = [0]*n
for i in range(n):
if a in Z[i]:
c[i] = 1
return tuple(c)
def weight(u):
"""Computes the weight (number of 1's) in a boolean n-tuple.
Complexity: O(n).
"""
w = 0
for i in range(len(u)):
if u[i] == 1:
w = w+1
return w
def combinations(n,t):
"""Just for fun, this is Chase's method for generating the sequence
of all boolean n-tuples of weight t. This is described in Knuth "Generating
all Combinations" in The Art of Computer Science.
Simpler methods exists, but this one is very nice. (Go read Knuth to see
why...)
"""
s = n-t
a = [0]*s + [1]*(t)
w = [1]*(n+1)
if s > 0:
r = s
else:
r = t
while True:
yield a
j = r
if w[j] == 0:
while w[j] != 1:
w[j] = 1
j = j+1
if j == n:
raise StopIteration
w[j] = 0
if a[j] != 0: # case C4 from Knuth
if j % 2 == 1 or a[j-2] != 0:
a[j-1], a[j] = 1, 0
if r == j and j > 1:
r = j-1
elif r == j-1:
r = j
next
else: # case C5 from Knuth
a[j-2], a[j] = 1, 0
if r == j:
r = max(j-2,1)
elif r == j-2:
r = j-1
next
else:
if j % 2 == 0 or a[j-1] != 0: # case C6 from Knuth
a[j], a[j-1] = 1, 0
if r == j and j > 1:
r = j-1
elif r == j-1:
r = j
next
else: # case C7 from Knuth
a[j], a[j-2] = 1, 0
if r == j-2:
r = j
elif r == j-1:
r = j-2
next
def counter_example_section(N,X,Y):
"""X / Y are tuples of sets (of the same length).
The function looks for a counter-example to X ⊑ Y as described in
the paper "Some Properties of Inclusions of Multisets and Contractive
Boolean Functions".
If no such counter-example is found, it returns None.
Otherwise, it returns a pair (s, u) where:
- s is a list (a,i) with a ∈ X_i
- u gives in which Y_i's the elements "a" above are : it should contain
less "1" than there were "a".
"""
# just checking the arguments are OK
n = len(X)
assert len(Y) == n
# the set of elements
N = set([])
for i in range(n):
N = N.union(X[i],Y[i])
########################################
### The algorithm really starts here
###
F = {} # This is the boolean function we are
# constructing.
# This is a finite map with at most 2^n elements,
# access is logarithmic: complexity O(log(2^n)) = O(n)
zeros = tuple([0]*n) # the (0,...,0) n-tuple
### we compute all the χ_X(a) and χ_Y(a) and put the appropriate values in
### the function F
###
for a in N: # complexity: c times
chiX = chi(a,X) # n log(x)
chiY = chi(a,Y) # + n log(y)
F[chiY] = sup(F.get(chiY,zeros) , chiX) # + 2n
### We generate all the boolean n-tuples, in order of increasing weights
### in order to "saturate" the (possibly partial) function F into an
### increasing function.
### Everytime we have a new value, we check if it satisfies the weight
### condition.
for w in range(n+1): # generating all tuples
for u in combinations(n,w): # complexity : about 2^n times
v = list(F.get(tuple(u),zeros)) # n
for i in range(n): # + n times
if u[i] == 1:
u[i] = 0
v = sup(v,F[tuple(u)]) # n^2
u[i] = 1
F[tuple(u)] = v
if weight(v) > w: # + n
### We've found a contradiction.
### We now look for some a's in N which gave this
### contradiction...
u = tuple(u)
l = []
v_acc = [0]*n
fv_acc = [0]*n
for a in N:
chi_X = chi(a,X)
chi_Y = chi(a,Y)
if sup(chi_Y,u) == u: # if chi(a,Y) less u
for i in range(n):
if chi_X[i] == 1 and v_acc[i] == 0:
l.append((a,i))
v_acc[i] = 1
fv_acc = sup(fv_acc, chi_Y)
if len(l) > w:
break
return (fv_acc, l)
### If we reach this far, it means the condition is satisfied for all
### values: we do have X ⊑ Y and there are no counter-examples!
return None
def print_set(Z, prefix=""):
"""prints the elements of a set"""
s = ""
for a in Z:
s = s + str(a) + " "
s = prefix + "{ " + s + "}"
print(s)
def show_counter_example(X,Y,v,l):
"""Shows the counter-example found by the function
"counter_example_section".
"""
n = len(X)
print("Counter-example found for")
for i in range(n):
print_set(X[i], " X_%d = " % i)
print("and")
for i in range(n):
print_set(Y[i], " Y_%d = " % i)
print("We have the following (partial) section in the X's")
for (a,i) in l:
print(" %d ∈ X_%d" % (a,i))
print("but these elements can only appear in %d Y's:" % weight(v))
for i in range(n):
if v[i] == 1:
print(" Y_%d" % i)
#tests
if __name__ == "__main__":
print("Doing a tiny bit of testing.")
print("")
N = set([1,2,3])
X = [set([1,2,3]) , set([2])]
Y = [set([1,2]) , set([2,3])]
r = counter_example_section(N, X, Y)
assert r == None
X = [set([1,3]) , set([2])]
Y = [set([1,2]) , set([2,3])]
r = counter_example_section(N, X, Y)
assert r == None
X = [set([1,3]) , set([3,2])]
Y = [set([1,2]) , set([2,3])]
r = counter_example_section(N, X, Y)
assert r != None
show_counter_example(X,Y,r[0],r[1])
print("")
N = set([1,2,3,4,5,6,7])
X = [set([1,2,3,4,5,6,7]), set([3,5,6]), set([7])]
Y = [set([4,5,6,7]),set([2,3,6,7]),set([1,3,5,7])]
r = counter_example_section(N, X, Y)
assert r == None
X = [set([1,2,3,4,5,6,7]), set([3,5,6,7]), set([7])]
Y = [set([4,5,6,7]),set([2,3,6,7]),set([1,3,5,7])]
r = counter_example_section(N, X, Y)
assert r == None
X = [set([1,2,3,4,5,6,7]), set([3,4,6,7]), set([7])]
Y = [set([4,5,6,7]),set([2,3,6,7]),set([1,3,5,7])]
r = counter_example_section(N, X, Y)
assert r != None
show_counter_example(X,Y,r[0],r[1])
print("")
print("OK, nothing too bad happened.")