# encoding: -utf8-
# Note: it needs 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 check_order(N,n,X,Y):
    """N is a set, n is an integer and X / Y are n-tuples of non empty
subsets of N. The function returns True or False depending on whether
X ⊑ Y as described in the paper "Some Properties of Inclusions of Multisets
and Contractive Boolean Functions".
"""

    def sup(u,v):           # complexity: O(n)
        """Computes the sup of two boolean tuples of size n."""
        w = [0]*n
        for i in range(n):
            w[i] = u[i] or v[i]
        return tuple(w)

    def chi(a,Z):           # complexity: O(n log(z))   (z is cardinality of Z)
        """Computes χ(a) of a wrt the n-tuple of sets Z."""
        c = [0]*n
        for i in range(n):
            if a in Z[i]:
                c[i] = 1
        return tuple(c)

    def weight(u):          # complexity: O(n)
        """Computes the weight (number of 1's) in a boolean n-tuple."""
        w = 0
        for i in range(n):
            if u[i] == 1:
                w = w+1
        return w


    def combinations(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


    ########################################
    ### 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(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
                return False    # condition isn't satisfied, we're finished

    ### If we reach this far, it means the condition is satisfied for all
    ### values: we do have X ⊑ Y!
    return True


# small test
if __name__ == "__main__":

    print("Doing a tiny bit of testing.")

    print("  test 1")
    N = set([1,2,3])
    n = 2
    assert check_order(N, n, (set([1,2,3]),set([2])), (set([1,2]),set([2,3])))
    assert check_order(N, n, (set([1,3]),set([2])), (set([1,2]),set([2,3])))
    assert not check_order(N, n, (set([1,3]),set([3,2])), (set([1,2]),set([2,3])))

    print("  test 2")
    N = set([1,2,3,4,5,6,7])
    n = 3
    assert check_order(N, n, (set([1,2,3,4,5,6,7]), set([3,5,6]), set([7])), (set([4,5,6,7]),set([2,3,6,7]),set([1,3,5,7])))
    assert check_order(N, n, (set([1,2,3,4,5,6,7]), set([3,5,6,7]), set([7])), (set([4,5,6,7]),set([2,3,6,7]),set([1,3,5,7])))
    assert not check_order(N, n, (set([1,2,3,4,5,6,7]), set([3,4,6,7]), set([7])), (set([4,5,6,7]),set([2,3,6,7]),set([1,3,5,7])))

    print("OK, nothing too bad happened.")