Cartesian on NULL arrays

Question

I need a cartesian product of 6 arrays - the catch is that at any time upto 5 arrays could be null. It works great when all arrays are populated but bombs when any of the arrays are null

my arrays are something like this

MatrixArray_1[0] = 1
MatrixArray_1[1] = 2

MatrixArray_2[0] = null
MatrixArray_2[1] = null

MatrixArray_n[0] = 2
MatrixArray_n[1] = 2

etc.

I am using this code currently...derived from http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

var product1 =  from first in MatrixArray_1
                from second in MatrixArray_2
                from third in MatrixArray_3
                from fourth in MatrixArray_4
                from fifth in MatrixArray_5
                from sixth in MatrixArray_6
                select new[] { first, second, third, fourth, fifth, sixth };
            string[][] myCombos_linq = product1.ToArray();

I have tried putting MatrixArray_n where first != null but that stops at the first null array and does not read thru all the remaining arrays so my return array is always 0 rows even though array1 and array 3 are populated.

Change of code/logic anything is appreciated at this point in time! TIA

Answer 1

Since Eric's approach is to use an IEnumerable<IEnumerable<T>>, you must be doing something like this:

Eric's code:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
  return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) => 
      from accseq in accumulator 
      from item in sequence 
      select accseq.Concat(new[] {item})); 
}

Call site:

var sequences = new int?[][] { MatrixArray_1, MatrixArray_2, ..., MatrixArray_6 };
var cartesianSequence = sequences.CartesianProduct();

Change the call site:

var cartesianSequence = sequences.Where(a => a.Any(e => e != null)).CartesianProduct();

The Where call will exclude sequences where all elements are null.

To exclude null arrays as well as arrays containing only null values:

var cartesianSequence = sequences.Where(a => a != null && a.Any(e => e != null)).CartesianProduct();

Or, with query comprehension:

var filteredSequences = 
    from sequence in sequences
    where sequence != null && sequence.Any(e => e != null)
    select sequence
var cartesianSequence = filteredSequences.CartesianProduct();

EDIT

Another possibility is that you want to exclude null elements of each sequence, even if some elements are non-null:

var filteredSequences = 
    from sequence in sequences
    where sequence != null && sequence.Any(e => e != null)
    select (from v in sequence where v.HasValue select s)
var cartesianSequence = filteredSequences.CartesianProduct();

OR

var cartesianSequence = sequences
    .Where(s => s != null && s.Any(e => e != null))
    .Select(s => s.Where(v => v != null))
    .CartesianProduct();

But it's hard to know exactly what to advise since we don't know what you're doing with the result.

Answer 2

Am I understanding correctly that you want to exclude any of first, second, etc. if they are null? That's easy:

Just add

select new [] { first, second, third, fourth, fifth, sixth }.Where(x => x != null)

to your query.

Or is that you want to exclude the entire sextuple if any of first, second, etc. are null? That's easy too. Just add

where new [] { first, second, third, fourth, fifth, sixth }.All(x => x != null)

to your query. You can even use let so you're not creating the array twice.

Answer 3

By definition (and I am quoting from the previously mentioned Eric Lippert blog). "The Cartesian product of two sequences S1 and S2 is the sequence of all possible two-element sequences where the first element is from S1 and the second element is from S2."

If you generalize the definition it would be:

The Cartesian product of any n sequences S1, S2,...Sn is the sequence of all possible n-element sequences where the first element is from S1 and the second element is from S2 and the N element is from Sn

Note that the first element should ALWAYS be from the first element.

If you are filtering out null values of the first array that means that the whole entery would be missing, the filtered out enterys looks like this:

(null, x2,...xn)

Here is a complete example:

array1 = {null, 1, 2}
array2 = {A}

The Cartesian product of array1 & array2 = { {null, A}, {1, A}, {2, A} }

Now, let's apply the filter where First != null.

The Cartesian product of array1 & array2 = {{1, A}, {2, A}}

Say that we changed the value of array1 to:

array1 now = {null, null}

The Cartesian product of array1 & array2 with the filter = {}

The result is empty set. In order to have a cartesian product, you have to have an entery from each array. Your question could be adjusted to address this fact.