https://d.puremagic.com/issues/show_bug.cgi?id=9106
--- Comment #16 from Joseph Rushton Wakeling <[email protected]> 2014-03-23 11:56:05 PDT --- (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] -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
