This post is long, contains hand made result for the expected values for 2, 3 and 4, you've been warned. I used the exact results instead of general proof, because the proof showed by Google analysis seems to make people stay skeptic. Have fun:
Let E(n) be the expected number of hits needed to sort n elements, where none of the n elements are in the correct place but all n correct places are present, i.e., every box has a non zero probability of getting sorted with each hit. I guess we can agree that E(0) = 0, even though this case is sort of abstract, no one should argue that to sort 0 elements no hits are needed. As Eagle say E(1) is irrelevant, it should never be used for anything, so I'l just skip it. For case [2 1], after one hit, we can get 1 2 --> Which can be expressed as E(0). 2 1 --> Which can be expressed as E(2), again. So E(2) is the probabilities multiplied by their expected values plus one (the hit we need to give the table to move from [2 1]) E(2) = 1/2 * E(0) + 1/2 * E(2) + 1 = 1/2 * 0 + 1/2 * E(2) + 1 = 1/2 * E(2) + 1 E(2) - 1/2 * E(2) = 1 E(2) * (1 - 1/2) = 1 1/2 * E(2) = 1 E(2) = 1 / (1/2) = 2 Now, for the case [3 1 2] 1 2 3 --> Which can be expressed as E(0). 1 3 2 --> Which can be expressed as E(0) + E(2), since the 1 is in it's position. 2 1 3 --> Which can be expressed as E(0) + E(2), since the 3 is in it's position. 2 3 1 --> Which can be expressed as E(3), again. 3 1 2 --> Which can be expressed as E(3), again. 3 2 1 --> Which can be expressed as E(0) + E(2), since the 2 is in it's position. So, E(3) = 1/6 * E(0) + 3/6 * (E(0) + E(2)) + 2/6 * E(3) + 1= 1/2 * E(2) + 1/3 * E(3) + 1 = 1/2 * 2 + 1/3 * E(3) + 1 = 2 + 1/3 * E(3) E(3) * (1 - 1/3) = 2 E(3) = 2 / (2/3) = 3 Finally, case [4 1 2 3], this are the 4! = 24 possible outcomes 1 2 3 4 --> Which can be expressed as E(0). 1 2 4 3 --> Which can be expressed as E(0) + E(0) + E(2), since 1 and 2 are at correct positions. 1 3 2 4 --> Which can be expressed as E(0) + E(0) + E(2), since 1 and 4 are at correct positions. 1 3 4 2 --> Which can be expressed as E(0) + E(3), since 1 is at correct position. 1 4 2 3 --> Which can be expressed as E(0) + E(3), since 1 is at correct position. 1 4 3 2 --> Which can be expressed as E(0) + E(0) + E(2), since 1 and 3 are at correct positions. 2 1 3 4 --> Which can be expressed as E(0) + E(0) + E(2), since 3 and 4 are at correct positions. 2 1 4 3 --> Which can be expressed as E(4), again. 2 3 1 4 --> Which can be expressed as E(0) + E(3), since 4 is at correct position. 2 3 4 1 --> Which can be expressed as E(4), again. 2 4 1 3 --> Which can be expressed as E(4), again. 2 4 3 1 --> Which can be expressed as E(0) + E(3), since 3 is at correct position. 3 1 2 4 --> Which can be expressed as E(0) + E(3), since 4 is at correct position. 3 1 4 2 --> Which can be expressed as E(4), again. 3 2 1 4 --> Which can be expressed as E(0) + E(0) + E(2), since 2 and 4 are at correct positions. 3 2 4 1 --> Which can be expressed as E(0) + E(3), since 2 is at correct position. 3 4 1 2 --> Which can be expressed as E(4), again. 3 4 2 1 --> Which can be expressed as E(4), again. 4 1 2 3 --> Which can be expressed as E(4), again. 4 1 3 2 --> Which can be expressed as E(0) + E(3), since 3 is at correct position. 4 2 1 3 --> Which can be expressed as E(0) + E(3), since 2 is at correct position. 4 2 3 1 --> Which can be expressed as E(0) + E(0) + E(2), since 2 and 3 are at correct positions. 4 3 1 2 --> Which can be expressed as E(4), again. 4 3 2 1 --> Which can be expressed as E(4), again. So... E(4) = 1 / 24 * E(0) + 6/24 * (2 * E(0) + E(2)) + 8/24 * (E(0) + E(3)) + 9/24 * E(4) + 1 = 6/24 * (0 + 2) + 8/24 * (0 + 3) + 9/24 * E(4) + 1 = 12/24 + 24/24 + 9/24 * E(4) + 1 E(4) * (1 - 9/24) = 36/24 + 1 = 60/24 E(4) = (60/24) / (15/24) = 60/24 * 24/15 = 60/15 = 4 Hope this helps to clarify the problem a little, at least, I hope it's length doesn't make the problem even more complicated, Carlos Guía On Tue, May 10, 2011 at 3:14 AM, Sarma Tangirala <[email protected]>wrote: > Second explanation +1! > > Sent from my BlackBerry > ------------------------------ > *From: * Vladimir Ignatyev <[email protected]> > *Sender: * [email protected] > *Date: *Mon, 9 May 2011 08:57:52 +0200 > *To: *<[email protected]> > *ReplyTo: * [email protected] > *Subject: *Re: [gcj] Re: Solution for Goro sort? > > In order to make it clear, it is better to start from permutation of just 2 > elements. > > Let’s first prove that average number of permutations in case of 2 unsorted > elements is 2.0. > > It is not so obvious, by the way. > > > > Initial position is {2,1}. After one Goro’s hit it may turn to {1,2} or > remain {2,1} with equal probabilities 1/2. > > If it’s remaining the same, then Goro will hit it again and, possibly, > again and again. > > > > Thus: > > There is probability 1/2, that Goro will sort two elements with 1 hit. > > There is probability 1/2*1/2 that, Goro will succeed after 2nd hit. > > There is probability 1/2*1/2*1/2 that, Goro will succeed after 3rd hit. > > And so on. > > > > Average number of hits is 1/2*1+1/2*(1/2*2+1/2*(1/2*3 + 1/2*(….)))))=2.0 > > > > As regards 3 non-sorted elements: > > Average number of permutation is 1/6 *1 + 3/6 * 3 + 2/6 * (1/6*2 + > 3/6*4+2/6*(….))))=3.0 > > > > Sorting of 4 elements required: > > 1/24*1+6/24*3+8/24*4+9/24*(1/24*2+6/24*4+8/24*5+9/24*(…..)))))=4.0 > permutations > > > Conclusion: In order to sort N elements Goro has to do N hits on average. > > > > Another explanation: > > If there are N free places where to fall, then there is probability 1/N > that after random permutation one element will find correct place. > Simultaneous permutation of N elements can be considered as N permutations > of single element, which is giving us one new sorted element after each hit. > > -- > 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. > > -- > 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. > -- 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.
