# 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.")