www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How to iterate all k-subsets of a range in a specific order?

reply "Tommi" <tommitissari hotmail.com> writes:
I can write the following in C++ to iterate through all 2-subsets 
of a forward-range in that specific order:

#include <iterator>
#include <boost/range/concepts.hpp>

template <typename R>
void fun(const R& r)
{
     BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<R> ));

     for (auto i = std::next(std::begin(r)); i != std::end(r); ++i)
     {
         for (auto j = std::begin(r); j != i; ++j)
         {
             _cprintf("%d %d", *j, *i);
         }
     }
}

But I can't see a generic way of accomplishing the same with D's 
forward-ranges. The following works only if the 'front' property 
of the range returns a reference:

import std.range;
import std.stdio;

void fun(R)(R r)
     if (isForwardRange!R)
{
     writeln("idx x y");

     auto idx = 0;
     auto rsaved = r.save;

     for (; !r.empty; r.popFront())
     {
         for (auto r2 = rsaved;
              &r2.front != &r.front; // front could return rvalue
              r2.popFront())
         {
             writefln("%s : %s %s", idx, r2.front, r.front);
             ++idx;
         }
     }
}

void main()
{
     auto r = [0, 1, 2, 3, 4];

     fun(r);
     readln();
}

Prints:
-------
idx x y
0 : 0 1
1 : 0 2
2 : 1 2
3 : 0 3
4 : 1 3
5 : 2 3
6 : 0 4
7 : 1 4
8 : 2 4
9 : 3 4


If you're wondering what's so special about that ordering of 
k-subsets, it's because then:

idx == x.nCr(1) + y.nCr(2)

...where nCr (n choose r) does what the homonym button in 
calculators does.

So, is there a generic way to write a function in D that 
corresponds to that C++ version, or is this a defect of the D's 
range concept?
Oct 05 2012
next sibling parent reply "Tommi" <tommitissari hotmail.com> writes:
Although, the only case, where this would be
a problem is with a range of type T, where:

1) It's impossible to provide random access to T
2) T can't return a reference from its 'front' property
3) T is a finite range (not infinite)
4) 'front' property may return the same value at different indexes

Something like:

struct R
{
     int _value = 0;
     int _round = 1;

      property bool empty() const
     {
         return _value == 100 && _round == 2;
     }

      property int front() const
     {
         return _value;
     }

     void popFront()
     {
         if (_value == 99)
         {
             if (_round == 1)
             {
                 _value = 0;
                 _round = 2;
             }
             else
             {
                 _value = 100;
             }
         }
         else
         {
             ++_value;
         }
     }
}

Albeit, in this simple example it would be possible to provide 
random access to R, because the sequential definition of it could 
be easily replaced with an algebraic one. But for a more complex 
sequential definition, it might not be possible. So, the 
situation, where this (potential) defect of the range concept 
would be a problem, seems very rare, but it's nevertheless 
possible.
Oct 05 2012
parent "Tommi" <tommitissari hotmail.com> writes:
Scratch all that. Even if range's 'front' property returned a 
reference, there's no guarantee that it references the same data 
as a copy of that range (created through the 'copy' property). 
So, my D version of that C++ function simply doesn't work... not 
even if 'front' is guaranteed to return a reference. Now this 
seems like a serious defect to me, please tell me I'm wrong.
Oct 05 2012
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/05/2012 01:08 AM, Tommi wrote:

 I can write the following in C++ to iterate through all 2-subsets of a
 forward-range in that specific order:

 #include <iterator>
 #include <boost/range/concepts.hpp>

 template <typename R>
 void fun(const R& r)
 {
 BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<R> ));

 for (auto i = std::next(std::begin(r)); i != std::end(r); ++i)
 {
 for (auto j = std::begin(r); j != i; ++j)
 {
 _cprintf("%d %d", *j, *i);
 }
 }
 }

 But I can't see a generic way of accomplishing the same with D's
 forward-ranges. The following works only if the 'front' property of the
 range returns a reference:

 import std.range;
 import std.stdio;

 void fun(R)(R r)
 if (isForwardRange!R)
 {
 writeln("idx x y");

 auto idx = 0;
 auto rsaved = r.save;

 for (; !r.empty; r.popFront())
 {
 for (auto r2 = rsaved;
 &r2.front != &r.front; // front could return rvalue
 r2.popFront())
 {
 writefln("%s : %s %s", idx, r2.front, r.front);
 ++idx;
 }
 }
 }

 void main()
 {
 auto r = [0, 1, 2, 3, 4];

 fun(r);
 readln();
 }

 Prints:
 -------
 idx x y
 0 : 0 1
 1 : 0 2
 2 : 1 2
 3 : 0 3
 4 : 1 3
 5 : 2 3
 6 : 0 4
 7 : 1 4
 8 : 2 4
 9 : 3 4


 If you're wondering what's so special about that ordering of k-subsets,
 it's because then:

 idx == x.nCr(1) + y.nCr(2)

 ...where nCr (n choose r) does what the homonym button in calculators 


does.

 So, is there a generic way to write a function in D that corresponds to
 that C++ version, or is this a defect of the D's range concept?


The != operator on the two ranges works for this case:

     for (; !r.empty; r.popFront()) {
         for (auto r2 = rsaved.save; r2 != r; r2.popFront()) {
             writefln("%s : %s %s", idx, r2.front, r.front);
             ++idx;
         }
     }

I tried it with an infinite range that is implemented as a struct, which 
in turn is passed through take():

struct FibonacciSeries
{
     int first = 0;
     int second = 1;

     enum empty = false;

      property int front() const
     {
         return first;
     }

     void popFront()
     {
         int third = first + second;
         first = second;
         second = third;
     }

     FibonacciSeries save() const
     {
         return this;
     }
}

     fun(FibonacciSeries().take(6));

That worked.

But when I tried it with an infinite range that is implemented as a 
class, the != operator failed because std.range.Take does not implement 
opEquals:

class SquaresRange
{
     int first;

     this(int first = 0)
     {
         this.first = first;
     }

     enum empty = false;

      property int front() const
     {
         return opIndex(0);
     }

     void popFront()
     {
         ++first;
     }

     SquaresRange save() const
     {
         return new SquaresRange(first);
     }

     int opIndex(size_t index) const
     {
         immutable integerValue = first + cast(int)index;
         return integerValue * integerValue;
     }

// Does have a special opEquals:

     override equals_t opEquals(Object o)
     {
         const rhs = cast(const SquaresRange)o;
         return rhs && (first == rhs.first);
     }
}

// Unfortunately this never stops:
     fun((new SquaresRange()).take(4));

I think if Take had an opEquals() defined, it could apply == explicitly 
on the range member that it uses for its iteration.

This brings up a question: Should all range types implement opEquals() 
for "range equality" as opposed to "identity equality" of the underlying 
range (i.e. Take.source in this case).

Ali
Oct 05 2012
parent reply "Tommi" <tommitissari hotmail.com> writes:
On Friday, 5 October 2012 at 09:37:51 UTC, Ali Çehreli wrote:

 This brings up a question: Should all range types implement 
 opEquals() for "range equality" as opposed to "identity 
 equality" of the underlying range (i.e. Take.source in this 
 case).


But even if the range concept was altered so that all ranges have 
to implement opEquals(), it wouldn't be a very satisfying 
solution. That's because opEquals() could be a very slow function 
for some ranges, e.g. forward ranges, where you have to check 
each element's equality one by one. Using opEquals() like that 
could make traversing those subset iterations very slow.
Oct 05 2012
parent "Tommi" <tommitissari hotmail.com> writes:
Uh... never mind. I guess this one was kind of like a magic 
trick; the solution was so obvious and simple I neglected it:


void fun(R)(R r)
     if (isForwardRange!R)
{
     writeln("idx x y");

     auto idx = 0;
     auto rsaved = r.save;

     for (size_t n = 0; !r.empty; r.popFront(), ++n)
     {
         size_t n2 = 0;

         for (auto r2 = rsaved; n2 < n; r2.popFront(), ++n2)
         {
             writefln("%s : %s %s", idx, r2.front, r.front);
             ++idx;
         }
     }
}
Oct 05 2012