https://d.puremagic.com/issues/show_bug.cgi?id=9106
--- Comment #17 from Ivan Kazmenko <[email protected]> 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/[email protected] 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: -------
