Re: Cartesian product of ranges?
On 14/12/11 9:21 PM, Timon Gehr wrote:
On 12/14/2011 09:14 PM, Justin Whear wrote:
I've looked through std.algorithm and std.range, but haven't found
anything
to compute the Cartesian product of several ranges. I have the nagging
feeling that this can be accomplished by combining several of the range
transformations in the standard library.
What I'm after is something like this:
alias Tuple!(int, string) P;
assert(equal(
cartesianProduct([1, 2], ["a", "b"]),
[ P(1, "a"), P(1, "b"), P(2, "a"), P(2, "b") ]
));
auto cartesianProduct(R,S)(R r, S s)if(isInputRange!R && isForwardRange!S){
struct CartesianProduct{
private{R r; S s, startS;}
this(R r, S s){this.r=r; this.s=s; startS=this.s.save;}
@property auto front(){return tuple(r.front, s.front);}
@property bool empty(){return r.empty;}
void popFront(){
s.popFront();
if(s.empty){
s = startS.save;
r.popFront();
}
}
static if(isForwardRange!R):
@property auto save(){return typeof(this)(r.save, s.save);}
}
return CartesianProduct(r,s);
}
The implementation of this was discussed at length a while ago.
The obvious implementation that you have above was presented, but Andrei
was unhappy that it didn't work well with infinite ranges. Some schemes
were investigated so that the products of two infinite ranges could
would get better sampling, but the whole thing got stuck in analysis
paralysis and nothing ever happened.
What you have above should be added into Phobos. If people want the
product of infinite ranges then they can just to it manually.
Re: Cartesian product of ranges?
On 12/14/2011 09:14 PM, Justin Whear wrote:
I've looked through std.algorithm and std.range, but haven't found anything
to compute the Cartesian product of several ranges. I have the nagging
feeling that this can be accomplished by combining several of the range
transformations in the standard library.
What I'm after is something like this:
alias Tuple!(int, string) P;
assert(equal(
cartesianProduct([1, 2], ["a", "b"]),
[ P(1, "a"), P(1, "b"), P(2, "a"), P(2, "b") ]
));
auto cartesianProduct(R,S)(R r, S s)if(isInputRange!R && isForwardRange!S){
struct CartesianProduct{
private{R r; S s, startS;}
this(R r, S s){this.r=r; this.s=s; startS=this.s.save;}
@property auto front(){return tuple(r.front, s.front);}
@property bool empty(){return r.empty;}
void popFront(){
s.popFront();
if(s.empty){
s = startS.save;
r.popFront();
}
}
static if(isForwardRange!R):
@property auto save(){return typeof(this)(r.save, s.save);}
}
return CartesianProduct(r,s);
}
Re: Cartesian product of ranges?
> See std.range.lockstep and std.range.zip. This suggestion was wrong, sorry. There is a need for a product in std.range, I think. Bye, bearophile
Re: Cartesian product of ranges?
On Wed, Dec 14, 2011 at 21:14, Justin Whear wrote: > I've looked through std.algorithm and std.range, but haven't found anything > to compute the Cartesian product of several ranges. I have the nagging > feeling that this can be accomplished by combining several of the range > transformations in the standard library. > > What I'm after is something like this: > > alias Tuple!(int, string) P; > assert(equal( > cartesianProduct([1, 2], ["a", "b"]), > [ P(1, "a"), P(1, "b"), P(2, "a"), P(2, "b") ] > )); I needed something like that a year or so ago. You can find it under the name 'combinations' : http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm.html Philippe
Re: Cartesian product of ranges?
Justin Whear: > alias Tuple!(int, string) P; > assert(equal( > cartesianProduct([1, 2], ["a", "b"]), > [ P(1, "a"), P(1, "b"), P(2, "a"), P(2, "b") ] > )); > See std.range.lockstep and std.range.zip. Bye, bearophile
Cartesian product of ranges?
I've looked through std.algorithm and std.range, but haven't found anything to compute the Cartesian product of several ranges. I have the nagging feeling that this can be accomplished by combining several of the range transformations in the standard library. What I'm after is something like this: alias Tuple!(int, string) P; assert(equal( cartesianProduct([1, 2], ["a", "b"]), [ P(1, "a"), P(1, "b"), P(2, "a"), P(2, "b") ] ));
