#! /usr/bin/python

def nextCount(s, maxval):
    # generates prod(maxval) states
    for i in reversed(xrange(len(s))):
        s[i] += 1
        if (s[i] <= maxval[i]):
            break
        s[i] = 0
    return s

def compatible(x, y):
    i = 0
    for target in x:
        total = 0
        while (i < len(y)):
            total += y[i]
            i += 1
            if (total == target):
                break
            if (total > target):
                return False
        else:
            return False
    return True

def shift(l,s):
    lsize = len(l)
    return [l[(i+s)%lsize] for i in xrange(lsize)]

class Permute:
    def __init__(self, set):
        self.state = []
        self.setCopy = [item for item in set]
        self.order = [item for item in set]

    def nextPermutation(self):
        self.state = nextCount(self.state, [i for i in reversed(xrange(len(self.state)))])

    def permutationsRemain(self):
        if (len(self.state) == 0):
            # handle first time
            self.state = [0 for item in self.setCopy]
            return True
        else:
            self.nextPermutation()
            if (sum(self.state) != 0):
                t = [item for item in self.setCopy]
                self.order = [t.pop(i) for i in self.state]
                return True
            else:
                self.state = []
                self.order = [item for item in self.setCopy]
                return False

def doubleDigest(seta, setb, setab, circular = False):
    a = Permute(seta)
    while (a.permutationsRemain()):
        ab = Permute(setab)
        while (ab.permutationsRemain()):
            if compatible(a.order, ab.order):
                b = Permute(setb)
                while (b.permutationsRemain()):
                    if (circular):
                        for i in xrange(len(setab)):
                            abShift = shift(ab.order, i)
                            if compatible(b.order, abShift):
                                return (a.order, b.order, ab.order, i)
                    else:
                        if compatible(b.order, ab.order):
                            return (a.order, b.order, ab.order, 0)
    return (aState, bState, abState, -1)

def main():
    print "Double Digest algorithm from Lecture 4"
    print "Enter restriction set A (with values separated by commas):"
    input = raw_input('Digest values: ')
    A = [int(val) for val in input.split(',')]
    print "Enter restriction set B (with values separated by commas):"
    input = raw_input('Digest values: ')
    B = [int(val) for val in input.split(',')]
    print "Enter restriction set AB (with values separated by commas):"
    input = raw_input('Digest values: ')
    AB = [int(val) for val in input.split(',')]

    aOrder, bOrder, abOrder, v = doubleDigest(A, B, AB)
    print " A = ", aOrder
    print " B = ", bOrder
    print "AB = ", abOrder

if __name__ == "__main__":
    main()