I'm trying to deepen my understand of probability, unions and intersections.
How would you go about finding the probability of x and y ( P(x U y) ??) for a collection of n objects (2 < n < 40) of unique heights, arranged along a line sequentially. Where x is the number of objects visible if you were to look from one direction along the line, and y is the number visible from the opposite direction?
It's a pretty good brain teaser I'm trying to wrap my head around. I wrote some python to help my generate some empirical evidence. I can easily brute force check the number of permutations up to n = 10, but above that permutations are n factorial, which gets large, quickly. So I'm trying to determine the probabilities for X and Y, or even the distinct counts themselves.
import itertools from collections import Counter import math f = math.factorial def answer(x,y,n): n = float(n) ans =  h =  counts1 =  counts2 =  perms =  for i in xrange(int(n)): h.append(i+1) for i in itertools.permutations(h,len(h)): count1 = 1 count2 = 1 perms.append(i) p1 = i p2 = i[-1] for j1,k1 in enumerate(i): if i[j1] > p1: p1 = i[j1] count1 += 1 counts1.append(count1) rev = [z for z in reversed(i)] for j2,k2 in enumerate(rev): if rev[j2] > p2: p2 = rev[j2] count2 += 1 counts2.append(count2) # print count1, i, count2 # print zip(counts1, counts2) c1 = Counter(counts1); print c1, "\n" cz = zip(counts1, counts2) czip = Counter(cz); print czip, "\n" combs = [i for i in itertools.combinations_with_replacement(h,2)] print "A \tC(A) \tP(A)" for i in combs: print i, "\t", czip[i], "\t", czip[i]/float(f(n)) answer1(x,y,n, c1) ans = czip[(x,y)] # print ans return ans, float(ans) / f(n) def answer1(x,y,n,c1): print "\n##### just calculations #####" f = math.factorial fn = float(f(n)) nn = int(fn/n) print "\n", "n =", n, "\n","n! =", math.factorial(n), "\n", "n!/n =", nn, "\n" px = c1[x] / fn print "P(X), x =", x,"\t", c1[x],"\t", px, "\t", px * nn py = c1[y] / fn print "P(Y), y =", y,"\t", c1[y],"\t", py, "\t", py * nn c1xORy = c1[x] + c1[y] pxORy = c1xORy / fn print "P(X or Y) \t", c1xORy, "\t", pxORy, "\t", pxORy * nn c1xANDy = abs(c1[x]-c1[y]) pxANDy = c1xANDy / fn # px + py - pxORy print "P(X and Y) \t",c1xANDy, "\t", pxANDy, "\t", pxANDy * nn, "\n"
Insight much appreciated.