• Justin Whear (10/10) Dec 14 2011 I've looked through std.algorithm and std.range, but haven't found anyth...
• bearophile (4/10) Dec 14 2011 See std.range.lockstep and std.range.zip.
• bearophile (4/5) Dec 14 2011 This suggestion was wrong, sorry.
• Philippe Sigaud (7/17) Dec 14 2011 ng
• Timon Gehr (19/29) Dec 14 2011 auto cartesianProduct(R,S)(R r, S s)if(isInputRange!R && isForwardRange!...
• Peter Alexander (9/42) Jan 01 2012 The implementation of this was discussed at length a while ago.

Justin Whear <justin economicmodeling.com> writes:

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") ]
));

bearophile <bearophileHUGS lycos.com> writes:

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

bearophile <bearophileHUGS lycos.com> writes:

 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

Philippe Sigaud <philippe.sigaud gmail.com> writes:

On Wed, Dec 14, 2011 at 21:14, Justin Whear <justin economicmodeling.com> w=
rote:
 I've looked through std.algorithm and std.range, but haven't found anythi=

ng
 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(
 =C2=A0 =C2=A0 =C2=A0 =C2=A0cartesianProduct([1, 2], ["a", "b"]),
 =C2=A0 =C2=A0 =C2=A0 =C2=A0[ 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

Timon Gehr <timon.gehr gmx.ch> writes:

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);
}

Peter Alexander <peter.alexander.au gmail.com> writes:

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.