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