Here is a pretty simple (and intuitive?) proof of the key lemma for the gorosort problem that on average a random permutation will have exactly one element in its correct slot. (Andre had a similar description of how to solve the problem.)
Lemma: If an array of N elements 1 .. N is randomly permuted (all permutations having been given equal probability), the expected number of elements that end up in their correct slots is exactly 1. Define Exact(i) to be the count of the number of permutations that have exactly i elements in their correct slots. (For N=3, Exact(0) = 2, Exact(1) = 3, Exact(2) = 0, Exact(3) = 1.) By definition, the desired expected value is sum <i = 0 to N> (i * prob(i)) where "i" is the number of elements in their correct slots and prob(i) is the probability of getting a permutation with "i" elements in their correct slots. (For N=3, that is 0 * 2/6 + 1 * 3/6 + 2 * 0/6 + 3 * 1/6) Note that prob(i) is just Exact(i) / (N!) So the expectation is (1/N!) * sum <i = 0 to N> (i * Exact(i)) Observe that "i * Exact(i)" is just the total number of elements in correct slots among the permutations that have exactly i values in correct slots. For N=3 and i=1, these are the three elements marked by asterisks: 1* 3 2, 3 2* 1, 2 1 3*. The sum of these quantities is the total number of elements across all permutations that are in their correct slots. But that quantity is N!. Here's a proof: Consider slot 1 of the array. There will be (N-1)! permutations that have 1 in slot 1, since we can have all of the (N-1)! permutations of the remaining values in slots 2 .. N. In general, for each slot k among the N slots, there are (N-1)! permutations that have value k in slot K. So, we have N * (N-1)! instances of a value k being in slot K. So, the expected number of elements in their correct slots is (N!) / (N!) or 1. Greg Johnson -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
