Random choice

The following function prints (in order) k random elements from the first n elements of the array A. In the program, k is the number of entries that still need to be printed, and n is the number of elements yet to be examined. The decision of whether to print the ith element is determined by the test rand() < k/n.

   function choose(A, k, n, i) {
          for (i = 1; n > 0; i++)
                if (rand() < k/n--) {
                       print A[i]
                       k--
                }
          }
   }