[Issue 9106] Rename std.random.randomShuffle as std.random.shuffle and small usage change

[d-bugmail at puremagic.com]

https://d.puremagic.com/issues/show_bug.cgi?id=9106



--- Comment #15 from Ivan Kazmenko <gassa at mail.ru> 2014-03-23 08:10:27 PDT ---
(In reply to comment #14)

> The rationale that I can see for randomCover would be that it ought to provide
> a non-destructive (i.e. no in-place shuffling), non-allocating (i.e. no
> .dup-ing or .save-ing of the original range) way of getting a random
> permutation of the elements of the range provided as input.
> 
> However, currently randomCover fails on the second of these in any case,
> because it contains and allocates an internal array of bools, _chosen.
> 
> I think that to be honest we simply need to do research and identify a better
> algorithm than the one currently implemented.  One such must exist.

I don't think a no-allocation version would be possible at all.  Consider
having already covered N/2 elements out of N elements.  There are Choose (N,
N/2) possible ways to do so.  To provide the next element, and then again and
again, N/2 more times, we have to remember that exact state somehow.  Hence we
have to store at least log (Choose (N, N/2)) bits at that moment to distinguish
between the states, which is of the order N/2.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------