#! /usr/bin/python

def nextCombination(v, slots):
    for i in xrange(len(v)-1,-1,-1):
        v[i] += 1
        if (sum(v) > slots - len(v)):
            v[i] = 0
        else:
            break
    return v

class intsFromL:
    def __init__(self, L, c):
        self.state = list()
        t = [x for x in L]
        t.sort()
        self.high = t[-1]
        del t[-1]
        self.intList= [t[0]]
        for i in xrange(1,len(t)):
            if (t[i] != self.intList[-1]):
                self.intList.append(t[i])
        self.count = c

    def intSet(self):
        v = [0]
        offset = 0
        for i in xrange(len(self.state)):
            offset += self.state[i]
            v.append(self.intList[offset+i])
        v.append(self.high)
        return v

    def combinationsRemain(self):
        if (len(self.state) == 0):
            # handles first time
            self.state = [0 for i in xrange(self.count)]
            return True
        else:
            nextCombination(self.state, len(self.intList))
            return (sum(self.state) != 0)

N = 0

def allPairsDist(L):
    global N
    N = N + 1
    dist = list()
    for i in xrange(len(L)):
        for j in xrange(i+1,len(L)):
            dist.append(L[j] - L[i])
    return dist


def anotherBruteForcePDP(L, n):
    L.sort()
    M = max(L)
    X = intsFromL(L,n-2)
    while (X.combinationsRemain()):
        dX = allPairsDist(X.intSet())
        dX.sort()
        if (dX == L):
            print "X = ", X.intSet()


import math

def main():
    print "Python version of Another Brute Force PDP algorithm on page 88"
    print "Enter digest values (separated by commas):"
    input = raw_input('Digest values: ')
    L = sorted([int(val) for val in input.split(',')])
    print L

    d = len(L)
    n = (math.sqrt(8*d + 1) + 1)/2
    if (int(n) != n):
        print "Invalid digest size"
    else:
        anotherBruteForcePDP(L, int(n))
    print N, " Iterations required"

if __name__ == "__main__":
    main()