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.
