www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - More general Cartesian product

reply Magnus Lie Hetland <magnus hetland.org> writes:
Hi!

I have a need for a Cartesian product of multiple ranges. I see there's 
been a discussion here (Dec 2011) as well as a request posted (#7128). 
It seems to me that the request deals with a multidimensional product 
-- which is what I need -- while the implementation by Timon Gehr deals 
only with the two-dimensional case.

I guess I could apply it in a nested fashion, but there's still the 
issue of flattening the result.

My application is a template along the lines of

  void forall(alias func, T...)(T args) {
    ...
  }

which would call func with every combination of parameters taken from 
the ranges in args. So that, for example, forall!foo([1, 2], ["a", 
"b"]) would yield four calls, from foo(1, "a") to foo(2, "b").

But the thing is that I'd like an arbitrary number of arguments. Sure, 
I could set an upper limit and hard-code the cases -- but there must be 
a prettier way? I've made some stabs at a recursive version, DMD 
complaining all the while. Any pointers?

(Now, I would eventually like to do more complex versions, using only a 
*subset* of the Cartesian product (for, e.g., all-pairs testing or 
combinatorial testing).)

-- 
Magnus Lie Hetland
http://hetland.org
Feb 29 2012
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
--00248c71178564209004ba1b1acf
Content-Type: text/plain; charset=UTF-8

 I have a need for a Cartesian product of multiple ranges. I see there's

seems to me that the request deals with a multidimensional product -- which is what I need -- while the implementation by Timon Gehr deals only with the two-dimensional case. I have one in a dsource project: http://www.dsource.org/projects/dranges It's in the algorithm.d module, look for 'combinations' Docs are there: http://svn.dranges.org/projects/dranges/trunk/dranges/doc/algorithm.html For a generalization of this, you may want to have a look into the rangeofranges.d module (docs: same than algorithm, or click on the 'package' tab on the left). I think a .zip is given on the main page. Alternatively, it's also on github: www.github.com/PhilippeSigaud/dranges --00248c71178564209004ba1b1acf Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <p><br> &gt; I have a need for a Cartesian product of multiple ranges. I see there&= #39;s been a discussion here (Dec 2011) as well as a request posted (#7128)= . It seems to me that the request deals with a multidimensional product -- = which is what I need -- while the implementation by Timon Gehr deals only w= ith the two-dimensional case.</p> <p>I have one in a dsource project:</p> <p><a href=3D"http://www.dsource.org/projects/dranges">http://www.dsource.o= rg/projects/dranges</a></p> <p>It&#39;s in the algorithm.d module, look for &#39;combinations&#39;</p> <p>Docs are there:</p> <p><a href=3D"http://svn.dranges.org/projects/dranges/trunk/dranges/doc/alg= orithm.html">http://svn.dranges.org/projects/dranges/trunk/dranges/doc/algo= rithm.html</a></p> <p>For a generalization of this, you may want to have a look into the range= ofranges.d module (docs: same than algorithm, or click on the &#39;package&= #39; tab on the left).</p> <p>I think a .zip is given on the main page.<br> Alternatively, it&#39;s also on github:</p> <p><a href=3D"http://www.github.com/PhilippeSigaud/dranges">www.github.com/= PhilippeSigaud/dranges</a><br><br></p> --00248c71178564209004ba1b1acf--
Feb 29 2012
parent Magnus Lie Hetland <magnus hetland.org> writes:
On 2012-02-29 14:24:36 +0000, Philippe Sigaud said:

 [snip]

In the meantime, I also hacked together a simple version of what I needed (see below), but I'll look into the references you provided as well :) void forall(alias func, size_t lvl=0, T...)(T args) { static if (lvl == args.length) { func(args); } else { foreach (e; args[lvl]) { forall!(func, lvl+1) (args[0..lvl], e, args[lvl+1..$]); } } } -- Magnus Lie Hetland http://hetland.org
Feb 29 2012