#! /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 intsBetween:
    def __init__(self, l, h, c):
        self.state = list()
        self.low = l
        self.high = h
        self.count = c

    def intSet(self):
        v = [self.low]
        for i in xrange(len(self.state)):
            v.append(v[i]+self.state[i]+1)
        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, self.high - self.low - 1)
            return (sum(self.state) != 0)

N = 0

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


def bruteForcePDP(L, n):
    L.sort()
    M = max(L)
    X = intsBetween(0,M,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 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:
        bruteForcePDP(L, int(n))
    print N, " Iterations required"

if __name__ == "__main__":
    main()