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:
  • What is the probability that exist k such that A[k] = k?
  • What is the probability the A is still sorted?
Pubblicato da a
Reazioni: 

1 comment:

  1. 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

Subscribe to: Post Comments (Atom)