Generate a subset in a uniformly random manner

21 Feb

Question: To generate a K-subset in a uniformly random manner from N elements.

We have two slightly different solutions. The first one is quite straightforward:  shuffle the elements, and then return the first K elements. In such solution, the space complexity would be O(N).

The second method would use the “inside-out” version of the shuffle. In this implementation, we travel the input from begin to end, rather than from end to begin. Every element has only one chance to enter the K-subset, when in its scanning stage. Otherwise, every processed element can only be swapped into latter position. As a result, once an element is swapped out of the K-subset, it could NEVER come back. And we do not need to keep it in record. The space complexity of this solution is O(K).

Leave a Reply

Your email address will not be published. Required fields are marked *