The problem of random sampling occurs in many different contexts. For example, we may wish to study experimentally the behaviour of a new data structure for searching. Then the easiest way is to generate a set of data elements, construct the corresponding structure and then perform searching of some elements belonging (or not belonging) to the data structure. A usual approach is to use a set of data elements where the elements are randomly sampled from a universal set. If we allow multiple occurrences of elements (sampling with replacement) we have no difficulties: we repeat m times a step where each of the possible n elements is chosen with equal probability 1/n (m being the size of the final multiset sample). If we demand in contrast to the above that each element occurs at most once in the sample (random sampling without replacement) the sampling may be very timeand space-consuming. Goodman and Hedetniemi give and analyse four sampling algorithms for this case.' The most effective of those, called SELECT, needs an O(m) running time for actual sampling, O(n) running time for preprocessing and O(«) storage space. The significance of an algorithm of this kind becomes evident if we recall a result of Ref. 1: if we sample elements with replacement and accept only those which have not yet been selected, then for finding m different elements we have on average to sample n-22=n-m+i 1/^ elements. The value of this expression may be very large in comparison to m. In addition, the decision whether or not a new element is really accepted demands sorting or O(n) storage. In the following we give an algorithm using the basic idea of SELECT but consuming only O(m) storage. The running time of the algorithm is on average proportional to m and in the worst case proportional to m. In addition, a version demanding O(/w log m) time, both on average and in the worst case, is pointed out.