You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.
I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above...
...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...
Fisher-Yates [1] algorithm is proven to "produce an unbiased permutation: every permutation is equally likely".
Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place."
According to examples in the English Wikipedia, the method I described above is actually the Fisher-Yates method (and its naive implementation, and thus the O(n²) complexity), and the swapping method on everyone's minds was actually Durstenfeld's (optimization?), with O(n).
The initial code snippet intended to be Durstenfeld was erroneously an off-by-one Sattolo implementation, which then further solidifyed my suspicion that it had a bias, which Sattolo's implementation actually indeed has. The Durstenfeld method is however proven to be unbiased.
To add further confusion to the names in the issue, though some readers might not be able to verify due to the language barrier, the German Wiki states (claims?) Fisher-Yates is Durstenfeld's method with O(n), and the "naive" Fisher-Yates is labelled as the "direct" approach, with O(n²). The name Durstenfeld is not mentioned anywhere on the German Wiki. Though the names are different, the maths are the same in both English and German. I speak German and often read both versions of an article, in case anyone's wondering why I even brought up the topic.
Thank you for posting the link.
EDIT: I try not to post usernames in text, in case anyone ever changes their name.
EDIT2: I recommend to always positively increment an iterator from 0 to n-1, and use in-loop arithmetics to get the actual desired iterator/index you require. It's less performant, but I'd argue mistakes are less common.
