Second explanation +1! Sent from my BlackBerry
-----Original Message----- From: Vladimir Ignatyev <[email protected]> Sender: [email protected] Date: Mon, 9 May 2011 08:57:52 To: <[email protected]> Reply-To: [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. Simultaneouspermutation 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.
