sawine@2: """
sawine@2: Name: perfect_hashing - applies the two-level scheme to build a perfect hash function
sawine@2: 
sawine@2: Description: Perfect Hashing builds a perfect hash function.
sawine@2: 
sawine@2: Author: Eugen Sawin <sawine@me73.com>
sawine@2: """
sawine@2: 
sawine@2: def main():
sawine@2: 	args = parse_args()
sawine@2: 	N = args.n
sawine@2: 	k = args.k
sawine@2: 	s = [int(e) for e in args.s.split(',')]
sawine@2: 	perfect_hashing(N, len(s), k, s)
sawine@2: 
sawine@2: def hkx(N, n, k, x):
sawine@2: 	return ((k*x) % N) % n
sawine@2: 
sawine@2: def find_ki(N, mi, Wi):
sawine@2: 	def injective():
sawine@2: 		hx = []
sawine@2: 		for x in Wi:
sawine@2: 			thx = hkx(N, mi, ki, x)
sawine@2: 			if thx in hx:
sawine@2: 				return False
sawine@2: 			else:
sawine@2: 				hx.append(thx)
sawine@2: 		return True
sawine@2: 
sawine@2: 	ki = 1
sawine@2: 	while not injective():
sawine@2: 		ki += 1
sawine@2: 	return ki
sawine@2: 
sawine@2: def perfect_hashing(N, n, k, xi):
sawine@2: 	hx = {}
sawine@2: 	for x in xi:
sawine@2: 		hx[(k, x)] = hkx(N, n, k, x)
sawine@2: 		print "h%i(%i) = (%i * %i mod %i) mod %i = %i" % (k, x, k, x, N, n, hx[(k,x)])	
sawine@2: 	ml = []
sawine@2: 	sl = [] 
sawine@2: 	kl = []
sawine@2: 	for i in xrange(n):
sawine@2: 		Wi = [thx[0][1] for thx in hx.iteritems() if thx[1] == i]
sawine@2: 		bi = len(Wi)
sawine@2: 		mi = 2 * bi * (bi - 1) + 1
sawine@2: 		si = sum(ml)
sawine@2: 		ki = find_ki(N, mi, Wi)
sawine@2: 		ml.append(mi)
sawine@2: 		sl.append(si)
sawine@2: 		kl.append(ki)
sawine@2: 		print "\nW%i = " % i, Wi
sawine@2: 		print "=> b%i = %i" % (i, bi), "m%i = %i" % (i, mi), "s%i = %i" % (i, si), "k%i = %i" % (i, ki)
sawine@2: 		if bi > 1:
sawine@2: 			print "=> hk%i = (%i * x mod %i) mod %i" % (i, ki, N, mi)
sawine@2: 
sawine@2: 	print
sawine@2: 	for x in xi:
sawine@2: 		i = hx[(k, x)]
sawine@2: 		posx = sl[i] + hkx(N, ml[i], kl[i], x)
sawine@2: 		print "x = %i => pos(%i) = %i" % (x, x, posx)
sawine@2: 
sawine@2: from argparse import ArgumentParser
sawine@2: 
sawine@2: def parse_args():
sawine@2:     parser = ArgumentParser(description='Builds a perfect hash function.')
sawine@2:     parser.add_argument('n', type=int, help='size of the universe U')
sawine@2:     parser.add_argument('k', type=int, help='parameter k of the hash function')
sawine@2:     parser.add_argument('s', help='comma-separated values defining the given set S')
sawine@2:     return parser.parse_args()
sawine@2: 
sawine@2: if __name__ == "__main__":
sawine@2: 	main()