[Issue 11306] ordering for std.algorithm.cartesianProduct

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=11306

--- Comment #3 from hsteoh at quickfur.ath.cx ---
Here are some thoughts I had about how to approach this. This is probably still
incomplete, but I want to put this here so that it doesn't get lost.

If all n argument ranges are finite forward ranges, then we basically have
unconstrained cartesianProduct evaluation order, so we can potential have n!
different orderings for the output. These can probably be specified as a
compile-time array of indices (basically some permutation of [0, 1, 2, ...
(n-1)]).

If one of the argument ranges is a non-forward input range (and there cannot be
more than one such argument, otherwise it's not possible to compute the
cartesian product), then this range must always iterate the slowest, because
otherwise it's not possible to compute the cartesian product (some combinations
will be missed since we can't rewind the input range). So in this case,
assuming the remaining arguments are all finite forward ranges, then the user
may specify (n-1)! possible orderings of the output.

In either case, the implementation is not that difficult:
cartesianProduct.Result.popFront just traverses the ranges in a different order
than the argument order, as specified by the compile-time array of indices (a
permutation of [0, 1, 2, ... (n-2)]).

In essence, this amounts to permuting the argument ranges such that
lexicographic ordering corresponds with the ordering the user desires, with
.front permuting the elements of the tuple back into argument order.
Non-forward input ranges will always be pushed to the front of the permuted
arguments.

If there are any infinite ranges, they probably should also be pushed to the
front of the permuted arguments (and if there are both infinite arguments and
non-forward input ranges, then the latter must be among the infinite arguments,
and will always be pushed to the front of the arguments, otherwise it is
impossible to evaluate the cartesian product -- it is impossible to compute the
cartesian product of a finite non-forward input range with an infinite range).
All infinite ranges, except possibly for one, must be at least forward ranges.
Infinite ranges do not allow arbitrary reorderings, because there are only
limited traversal schedules that will cover all elements in the cartesian
product. While there is still some amount of flexibility here (esp. if you have
random access infinite ranges), this could lead to an explosion of complexity
in the implementation -- how will the user specify a certain ordering, for
example -- so I'm inclined to just say that the user cannot specify the
iteration ordering for infinite ranges.

So in summary, computing a cartesian product of n finite forward ranges with m
infinite ranges with a non-forward input range (there cannot be more than 1 of
the latter) amounts to:
- permuting the ranges to form the sequence (I,J1,J2,J3,...,K1,K2,K3...) where
I = non-forward input range, J1..Jm = infinite ranges, and K1..Kn = finite
forward ranges.
- Evaluating the cartesian product using the current ordering (i.e.,
lexicographic on K1..Kn, n-dimensional generalization of Andrei's
expanding-square schedule for J1..Jm, over each element of I)
- Permuting the resulting tuple back to argument order in .front.
- The user will be able to specify the ordering of K1..Kn in terms of which
ones should iterate faster than which others, but the evaluation order of
(I,J1..Jm) will be dictated by the implementation.

So far, the above steps are relatively easy to implement, except for the
n-dimensional generalization of Andrei's expanding square schedule for infinite
forward ranges. The only approach I can currently think of is equivalent to the
"old" variadic cartesianProduct implementation, which expands an exponential
number of templates -- clearly infeasible beyond the most trivial cases.

Having said that, though, I have trouble imagining what use cases there are for
generating n-order cartesian products of infinite ranges for large n -- it will
take forever to get to the combination you want, for example, and you might as
well use more direct methods of construction to get it!

--