- What is the probability that exist k such that A[k] = k?
- What is the probability the A is still sorted?
Saturday, March 21, 2009
An array of integers sorted and shuffled
You are given a sorted array A of N integers. For each integer i, a random number j is extracted and A[i], A[j] are swapped. When this shuffling is complete:
Subscribe to:
Post Comments (Atom)
The question of P( s[k]==k for some k) surprisingly comes up all the time in hash tables and sorting. It's a surprising result to most people that the probability converges to a nice value (1-1/e) and doesn't depend much on the size of the population. It's sort of like the Birthday paradox in its "really!??" counter-intuitiveness.
ReplyDelete