Let's say I have a sequence of items of unknown length, n. I want to randomize the order of this sequence without having to go through the entire sequence. Are there any algorithms that can do this?
I have 10 items in my sequence:
A B C D E F G H I J (though I don't know that I have 10). At the end of my randomization it would have ended up as
E G F B A I C D J H.
If I only wanted to know the first 3 random elements, I would get
E G F, and since G is the furthest element in the original sequence, I would never have to read the sequence past G.
My algorithm would, somehow, look at A and realize that it randomly belongs past the first 3 requested elements, it would then look at B and realize the same, ..., it would look at E and realize that it needs to randomly be the first element so it adds it to a return buffer as element 1, then F randomly should be the third element, so it adds it to a return buffer as element 3, then it hits G and adds that to the return buffer as element 2 and it completes. It never even looks at where H, I, or J should go.
3/nof being picked, which you can't know without knowing
n). If you want 'pick 3 elements uniformly at random from a sequence of known length without necessarily enumerating the whole sequence', this is doable.