[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 #17 from Ivan Kazmenko <gassa at mail.ru> 2014-03-23 13:10:11 PDT ---
(In reply to comment #16)
> (In reply to comment #15)
> > 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.
> 
> I think I may have struck gold in the search for appropriate algorithms:
> http://gan.anu.edu.au/~brent/pd/Arndt-thesis.pdf
> 
> It'll take some time to read and digest this and see if it's really a good
> source of potential algorithms, but I thought I'd share the reference in any
> case. 
>
> See also:
> http://forum.dlang.org/post/gn3vo8$vdt$1@digitalmars.com

The paper looks interesting (albeit likely for other purposes), thank you for
the link.

Regarding randomCover, Andrei's example with an LCG is able to generate only
few permutations of order n at all.  There are just a few dozen bits of
information if the initial state and the transition function of any LCG modulo
n.  Thus there will be O(Poly(n)) (say, n^3 if we choose seed, multiplier and
summand arbitrarily) different permutations possibly appearing in the LCG
generation process.  Still, there are n! different permutations of order n.

A good randomCover would be able to generate a uniformly distributed
permutation of any order n, provided that the underlying random bits are
uniform and independent (that is, from an ideal randomness source).  I believe
no algorithm would suffice to counter the proof above which states that we need
to store at least n bits during the course of randomCover.  And there does not
seem to be much justification in providing a skewed (that is, non-uniform)
randomCover in Phobos.

So, I believe the solution with least allocations would be to allocate once
when the randomCover struct/class is initialized (possibly with an option to
reuse space given in an extra argument), and then proceed allocation-free.  The
downside is that it will be always Theta(n) bits, while if we knew ahead the
maximum number of calls k to randomCover, Theta(k) memory would suffice.

-----

Well, that's offtopic here.  Is there a proper place to put it?  A wiki
discussion page, perhaps?  Forum threads tend to get lost...

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