How to iterate all k-subsets of a range in a specific order?

Tommi tommitissari at hotmail.com
Fri Oct 5 01:08:27 PDT 2012


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?


More information about the Digitalmars-d-learn mailing list