We consider the problem of randomly selecting $s$ different
$m$-element subsets of $\{1,...,k\}$.
The only known lower bound for this problem is the trivial $\Omega
(sm)$. The best two previously known solutions are of time $O(sm^2)$
and $O(s(k+m))$, respectively.
We present an algorithm for $k>s+m$ whose time complexity is
$O(sm\log m + s^2)$, and whose space requirement is $O(sm)$.
For $s\leq m$ this algorithm is almost optimal.
It has an added advantage over the $O(sm^2)$ algorithm in that it
operates in a conventional model of computation. It has a clear
advantage over the $O(s(k+m))$ algorithm for large $k$ (in fact that
latter algorithm also has space complexity $O(k+m)$).
(joint work with Imanuel Dar)