random pivot DP approach

random_pivot_dp.py

dp = {}
# computes the probability
# that the ith smallest element and the jth smallest element are compared
# considering 
# kth smallest, k + 1 th smallest element, ..., i th smallest .. j th smallest
# ... lth smallest element.
# using DP.
# 
def solve(k, l, i, j):
	# if this value has been computed already, simply return it.
	if (k, l) in dp: return dp[(k, l)]
	
	# there are l - k + 1 elements in total.
	constant =  1.0 / (l - k + 1)
	
	if k == i and l == j: 
		return 2.0 / (j-i+1)
	
	# Out of l - k + 1 potential pivots, 
	# 2 are good pivots. i.e. the ith and jth smallest elements.
	res = 2*constant
	
	# Pivots are chosen somewhere to the left of i.
	# In each case, you discard the half that does not contain i, # 
	# but compute the probability against the half that contains i, j.
	for a in xrange(k + 1, i + 1):
		res += constant*solve(a, l, i, j)
	
	# Pivots are chosen somewhere to the right of j.
	# same as above.
	for b in xrange(j, l):
		res += constant*solve(k, b, i, j)
	dp[(k, l)] = res
	return res

for size in xrange(10, 20):
	# the probability should be 2/(7-2+1) = 2/6 = 0.333
	# regardless of size 
	print solve(0, size, 2, 7)