Joseph Rushton Wakeling wrote:
It's probably worth investigating the algorithms out there for
this kind of functionality, because I doubt the algorithm
that's given is optimal.
Given that the lazy version will hardly be possible without
allocating O(n) additional memory anyway, the simple solution is:
- build a random permutation of iota(n) at start using
randomShuffle (instead of maintaining the private bool[] _chosen
array),
- lazily iterate the range according to the permutation.
It is n ints of memory instead of n bools which is comparable,
but O(n) initialization and O(1) per step which is definitely
better than now.
