QSort in D: is this best?

[Philippe Sigaud]

On Mon, Dec 21, 2009 at 23:44, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

> This is a great example that I don't have the time to look into now. In
> essence the task is to generate all numbers of the form 2^^a*3^^b*5^^c where
> a, b, and c are natural numbers.
>
> Currently Phobos doesn't have the means to compute the cross-product of
> ranges. I encourage people to think about implementing that.
>
> Andrei


I posted yesterday on D.announce that I have some code related to that:

http://www.dsource.org/projects/dranges

If some people are interested, I'd be delighted to have some feedback. The
docs for the algorithm module is here:

http://svn.dsource.org/projects/dranges/trunk/docs/algorithm2.html

There is a cross-product for ranges (returning tuples), called combinations.
As in,

auto c = combinations(r1, r2, r3, r4); // Takes a variadic number of ranges.



I put a Hamming numbers example in the docs, for the merge function.
>From the docs :

// Calculating Hamming numbers, numbers of the form 2^i * 3^j * 5^k
// see http://en.wikipedia.org/wiki/Regular_number
// Dijkstra's algorithm heavily uses merge.
T[] hamming(T)(T[] r)
{
    return 1 ~ *merge2*(map!"2*a"(r),*merge2*(map!"3*a"(r),map!"5*a"(r)));
}

auto hammingNumbers =  iterate!hamming([1UL][]); // develops the
Hamming sequence at each iteration.
// 1,2,3,4,5,6,8,9,10,12,...
// For the i-th iteration, the sequence is complete up to 2^i,
// but has much more numbers already calculated.

So I kind of cheat there: it's not Haskell's elegant self-recursive
definition, but it's very near Dijkstra's algorithm and can be made a
one-liner, if that's really a criteria... At each front call, iterate
extends the sequence.

merge2 is greedy and works only for two ranges (hence it's name), but I have
a templated, predicate-aliased, lazy, n-ranges version called merge in the
module.

   Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20091222/95effbc3/attachment.html>