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:
 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 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
Feb 29 2012
parent Magnus Lie Hetland <magnus hetland.org> writes:
On 2012-02-29 14:24:36 +0000, Philippe Sigaud said:

 [snip]

Thanks for the response. 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