Suppose you want to test every pairing of character class and weapon. Two nested loops will do it, but the underlying operation has a name: the Cartesian product. For sets A and B, A×B contains every pair whose first item comes from A and second from B. In SQL, this is a CROSS JOIN. section 6.1
Listing 6.3 The Cartesian product of two sequences
public static IEnumerable<(A a, B b)> CartesianProduct<A, B>(
this IEnumerable<A> seqa, IEnumerable<B> seqb)
{
foreach (var a in seqa)
foreach (var b in seqb)
yield return (a, b);
}
For sequences rather than sets, nested foreach loops and yield return enumerate the pairs without first building a result set. Duplicate input elements can therefore produce duplicate output pairs. section 6.1.1
A third loop can produce three-valued tuples. Simply applying a two-input product twice instead produces nested pairs: ((a, b), c). That distinction matters when choosing a result type. A variant also accepts a projection function, producing a value from each pair instead of returning the pair itself. section 6.1.1
What if the number of input sequences is known only at runtime? A fixed-size tuple no longer fits. Use a sequence of sequences of the same element type, and grow each partial result by one element per input sequence. The starting result is deliberately surprising: the product of zero sequences is one empty sequence, [[]]. It gives the first input something to extend; a single input then produces one-element sequences. An empty input sequence leaves no results to extend. section 6.1.2
Listing 6.5 A LINQ-based implementation of the arbitrary Cartesian product
public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
this IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IDeque<T>> result = [Deque<T>.Empty];
foreach (var sequence in sequences)
result = from deque in result
from item in sequence
select deque.PushRight(item);
return result;
}
The implementation starts with an empty deque. Each query pairs every partial result with every item in the next sequence, then appends that item. Aggregate can express the same progression without an explicit outer loop. section 6.1.2
Letters as independent choices
For the inputs "ABC", "DEF", and "GH", the output begins ADG, ADH, AEG, AEH and ends CFG, CFH. Each result chooses one character from each input; the product has 3×3×2 results. The same operation can rapidly generate test cases across independent choices. section 6.1.2 section 6.0
Repeatedly taking the product of the digits 0 through 9 gives digit strings in lexicographic order: with four positions, 0000 through 9999. This links product positions to decimal notation; other bases work similarly. A product explores independent choices, whereas a permutation reorders one sequence. section 6.1.3
