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

• Tommi (65/65) Oct 05 2012 I can write the following in C++ to iterate through all 2-subsets
• Tommi (46/46) Oct 05 2012 Although, the only case, where this would be
• Tommi (6/6) Oct 05 2012 Scratch all that. Even if range's 'front' property returned a
• =?UTF-8?B?QWxpIMOHZWhyZWxp?= (76/139) Oct 05 2012 The != operator on the two ranges works for this case:
• Tommi (7/11) Oct 05 2012 But even if the range concept was altered so that all ranges have
• Tommi (18/18) Oct 05 2012 Uh... never mind. I guess this one was kind of like a magic
"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);
}

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
"Tommi" <tommitissari hotmail.com> writes:
```Although, the only case, where this would be
a problem is with a range of type T, where:

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
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
"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
=?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);
}

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
"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
"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