https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #5 from hsteoh@quickfur.ath.cx ---
Hmm. Sounds like what you want is n-element subsets, rather than tuples specifically. I'll see if I can find any good algorithms for n-subset enumeration...

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #6 from bearophile_hugs@eml.cc ---
(In reply to hsteoh from comment #5)
> Hmm. Sounds like what you want is n-element subsets, rather than tuples specifically. I'll see if I can find any good algorithms for n-subset enumeration...

Isn't the code in comment #4 good enough?

(A pairwise range needs to be very efficient, so people can use it instead of two nested loops in more cases).

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #7 from hsteoh@quickfur.ath.cx ---
If order doesn't matter, then a series of nested loops should do what you want. However, we can't actually use nested loops for a generic algorithm, since (1) the nesting level depends on how many elements you want in the subset, and (2) we have to lazy-fy the loops to conform to the range API anyway. So I've to think of some equivalent way of enumerating these subsets...

I'm thinking that a forward range should be sufficient for such an enumeration. So if we have a stack of .save'd ranges, that should do the trick. First, to generate k-element subsets, we prime the stack with .save'd copies of the range up to the k'th element, then .front simply walks the stack and retrieves .front from each item on the stack. In popFront(), we simply advance the range at the top of the stack. If it's empty, we pop it off, and advance the previous range on the stack, then fill up the stack again with the subsequent element. Each time, if advancing a range makes it empty, we pop it off and advance the previous range on the stack instead, then fill up the stack again. Yes, I think this will work... PR time! :-)

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #8 from bearophile_hugs@eml.cc ---
(In reply to hsteoh from comment #7)

> If order doesn't matter,

The order matters, this:

foreach (tup; iota(1, 5).pairwise)
    tup.writeln;

Should print only in this order:

Tuple!(int,int)(1, 2)
Tuple!(int,int)(1, 3)
Tuple!(int,int)(1, 4)
Tuple!(int,int)(2, 3)
Tuple!(int,int)(2, 4)
Tuple!(int,int)(3, 4)


> However, we can't actually use nested loops for a generic algorithm, since (1) the nesting level depends on how many elements you want in the subset, and (2) we have to lazy-fy the loops to conform to the range API anyway.

The function name "pairwise" refers to "pairs", because 95% of the times I only need two indexes. And code like "[1, 2, 3, 4].pairwise" doesn't contain a "2" to specify two indexes.

So if you want to reduce your implementation work, you can just use the version that yields pairs, like in #Comment 4.

But if you want to also implement the generation of 3-tuples or more, then I guess you can use a syntax like:

iota(1, 5).pairwise!3

But now the name "pairwise" sounds like a falsity.


> I'm thinking that a forward range should be sufficient for such an enumeration.

We can make the range more powerful later, if necessary.


> So if we have a stack of .save'd ranges, that should do the
> trick. First, to generate k-element subsets, we prime the stack with .save'd
> copies of the range up to the k'th element, then .front simply walks the
> stack and retrieves .front from each item on the stack. In popFront(), we
> simply advance the range at the top of the stack. If it's empty, we pop it
> off, and advance the previous range on the stack, then fill up the stack
> again with the subsequent element. Each time, if advancing a range makes it
> empty, we pop it off and advance the previous range on the stack instead,
> then fill up the stack again. Yes, I think this will work... PR time! :-)

I suggest to add a compile-time optimization for the most general case (n=2) to make it fast, because it's the most common and it should be very fast.

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #9 from bearophile_hugs@eml.cc ---
This shows a simple use case of pairwise, to compute the pairs of closest points of an array 2D points.

The function closestPair1 uses just a pair of loops.

closestPair2 uses cartesianProduct of all index pairs plus a filter to avoid comparing already seen pairs (because a distance is comutative), the code is slow, it looks bad and it's noisy.

closestPair3 uses pairwise, and it's much nicer and simpler to write.

closestPair4 is similar, but it uses the optional "key" function argument (as in the Python min/max functions) to further simplify the code. I'd really like min/max of Phobos to be extended to support such optional key function.

Currently some /*in*/ are commented out to avoid troubles with immutable seeds of reduce.



import std.algorithm, std.traits, std.typecons, std.range;

struct Pairwise(Range) {
    alias R = Unqual!Range;
    alias Pair = Tuple!(ForeachType!R, "a", ForeachType!R, "b");
    R _input;
    size_t i, j;

    this(Range r_) {
        this._input = r_;
        j = 1;
    }

    @property bool empty() {
        return j >= _input.length;
    }

    @property Pair front() {
        return Pair(_input[i], _input[j]);
    }

    void popFront() {
        if (j >= _input.length - 1) {
            i++;
            j = i + 1;
        } else {
            j++;
        }
    }
}

Pairwise!Range pairwise(Range)(Range r)
if (isRandomAccessRange!Range && hasLength!Range && !isNarrowString!Range) {
    return typeof(return)(r);
}

//-----------------------

struct V2 { double x, y; }

double distance(in V2 p1, in V2 p2) pure nothrow @nogc @safe {
    return (p1.x - p2.x) ^^ 2 + (p1.y - p2.y) ^^ 2;
}

auto closestPair1(in V2[] points) pure nothrow @nogc @safe {
    auto minD = Unqual!(typeof(V2.x)).infinity;
    V2 minP1, minP2;
    foreach (immutable i, const p1; points.dropBackOne)
        foreach (const p2; points[i + 1 .. $]) {
            immutable d = distance(p1, p2);
            if (d < minD) {
                minD = d;
                minP1 = p1;
                minP2 = p2;
            }
        }
    return tuple(minP1, minP2);
}

auto closestPair2(/*in*/ V2[] points) pure nothrow @nogc @safe {
    auto pairs = cartesianProduct(points.length.iota, points.length.iota)
                 .filter!(ij => ij[1] > ij[0]);
    immutable ij = reduce!((ij1, ij2) =>
            distance(points[ij1[0]], points[ij1[1]]) <
            distance(points[ij2[0]], points[ij2[1]]) ? ij1 : ij2)
        (pairs.front, pairs.dropOne);
    return tuple(points[ij[0]], points[ij[1]]);
}

auto closestPair3(/*in*/ V2[] points) pure @safe {
    return points
           .pairwise
           .reduce!((t1, t2) => t1[].distance < t2[].distance ? t1 : t2);
}


template min(alias F) {
    T min(T)(T x, T y) {
        return F(x) < F(y) ? x : y;
    }
}

auto closestPair4(/*in*/ V2[] points) pure @safe {
    return points.pairwise.reduce!(min!(t => t[].distance));
}

void main() {
    import std.stdio, std.random;

    auto points = new V2[10];
    foreach (ref p; points)
        p = V2(uniform01, uniform01);

    points.writeln;
    points.closestPair1.writeln;
    points.closestPair2.writeln;
    points.closestPair3.writeln;
    points.closestPair4.writeln;
}

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #10 from bearophile_hugs@eml.cc ---
Elsewhere I have suggested to add to cartesianProduct an optional template argument that specifies the "repetitions", just like the Python version of product:

https://docs.python.org/2/library/itertools.html#itertools.product

Python code:

product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy

product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111


Equivalently for the D code (the "repeat" argument "3" needs to be a template argument because cartesianProduct yields tuples, that must have their structure known at compile-time):

cartesianProduct!3([0, 1]) => 000 001 010 011 100 101 110 111

Now I've seen the same optional repeat template argument is useful for pairwise too, because if you are inside a UFCS chain and you want to perform a pairwise on the sequence items, you don't need to break the chain:


auto seq = 10.iota
           .map!(...)
           .filter!(...);

auto result = pairwise(seq, seq)
              .filter!(...);


Becomes a single nicer chain:

auto result = 10.iota
              .map!(...)
              .filter!(...)
              .pairwise!2
              .filter!(...);


Such use case "pairwise(seq,seq)" with repeated argument is probably common.

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #11 from bearophile_hugs@eml.cc ---
(In reply to bearophile_hugs from comment #10)

>               .pairwise!2

pairwise takes only one argument sequence, so that comment was bad. The template argument is used to denote how many items you want in your "pairs" (where 2 is the default).

So:

[1, 2, 3, 4].pairwise
Or:
[1, 2, 3, 4].pairwise!2

should yield:

(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)


[1, 2, 3, 4].pairwise!3

should yield:

(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)


Like in this lower level code:

void main() {
    import std.stdio, std.range, std.algorithm;
    auto a = [1, 2, 3, 4];

    foreach (immutable i; 0 .. a.length)
        foreach (immutable j; i + 1 .. a.length)
            writefln("(%d, %d)", a[i], a[j]);

    writeln;

    foreach (immutable i; 0 .. a.length)
        foreach (immutable j; i + 1 .. a.length)
            foreach (immutable k; j + 1 .. a.length)
                writefln("(%d, %d, %d)", a[i], a[j], a[k]);
}

--

https://issues.dlang.org/show_bug.cgi?id=6788

Seb <seb@wilzba.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |seb@wilzba.ch

--

https://issues.dlang.org/show_bug.cgi?id=6788

Andrei Alexandrescu <andrei@erdani.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |bootcamp
                 CC|                            |andrei@erdani.com

--

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #12 from greenify <greeenify@gmail.com> ---
@andralex: I think there is also a decision-blocked PR pending in the Phobos queue:

https://github.com/dlang/phobos/pull/4027

--