Generating a row within a cross product given an integer

Question

I've got a problem I'm struggling with a bit. Given an arbitrary number of arrays and an integer called 'specificity', I need to generate the row representing that point within the cross product of the arrays. Arrays are always a length of at least 2 and the last value of each array is always null. No other elements are ever null except for the last in each array. For example, given the arrays {1, 2, null} and {A, B, null}, the cross product would effectively be:

0: 1 A
1: 1 B
2: 1 null
3: 2 A
4: 2 B
5: 2 null
6: null A
7: null B
8: null null

So, given 'specificity' 4 for example with the two arrays listed above, it should return back the array {2, B}. That's the easy part. I've completed this particular case in the code section below. However, consider the case where combinations without nulls take precedence. The ordering would now be:

0: 1 A
1: 1 B
2: 2 A
3: 2 B
4: 1 null
5: 2 null
6: null A
7: null B
8: null null

Here's the algorithm I've implemented so far. The first case above is handled just fine, but I don't know what to do for the second case. Any thoughts on what would go into the "else" clause?

    public static String generateKeyForSource(int specificity, KeySource keySource) {
    if (specificity > keySource.getNumPossibleKeys()) {
        throw new IllegalArgumentException("The specificity " + specificity + " is larger than the max number of possible keys for this KeySource, which is " + keySource.getNumPossibleKeys());
    }
    Object[][] hierarchies = keySource.getHierarchies();
    boolean combinedPrecedence = keySource.isCombinedPrecedence();

    int[] indexes = new int[hierarchies.length];
    int multiplier = 1;

    if (!(combinedPrecedence && specificity >= keySource.getFirstSpecificityContainingNull())) {
        for (int i = hierarchies.length - 1; i >= 0; i--) {
            Object[] hierarchy = hierarchies[i];
            int range;
            if (combinedPrecedence)
                range = hierarchy.length - 1;
            else
                range = hierarchy.length;

            int currentArrayIndex = specificity / multiplier % range;
            indexes[i] = currentArrayIndex;
            multiplier *= hierarchies[i].length;
        }
    }
    else {
        //?????????
    }

    return generateKey(indexes, hierarchies);
}

Answer 1

Induction is your friend when looking for solutions to this kind of problem.

For the easy case, it looks like

easy( a, i ) ≡ easyHelper( a, a.length, i )  
easyHelper( a, n, i ) ≡ easyInduction( easyHelper, 0 )( a, n, i )

easyInduction( f, b )( a, 0, 0 ) ≡ []  
easyInduction( f, b )( a, 0, i + 1 ) ≡ undefined
easyInduction( f, b )( a, n + 1, i ) ≡
   let t = a[n + 1].length - b
    in f( a, n, ⌊i / t⌋ ) ++ [ a[n + 1][i mod t] ]

For the hard case, I think you need a stronger inductive assumption. That is, your helper recursive method needs to return both an offset and a function mapping specificities to tuples. The function, when applied to indices below the offset, returns the member of the cross product of all the arrays with the nulls removed; above the offset the null cases start. Knowing this for the case of n arrays, you can construct the new offset and the new function for n + 1 arrays, via the following three cases:

1. you're less than the new offset, so you treat it like the easy case for the non-null members of the last array
2. you're between the new offset and the sum of the new and old offsets, so you should return the recursive result with a null on the end
3. you're bigger than the sum, so you again treat it like the easy case, except you make sure that the recursive calls therein use indices beyond the old offset

Here's my untested psuedo-code take on that.

hard( a, i ) ≡ hardHelper( a, a.length ).second( i )
hardHelper( a, 0 ) ≡ ( 1, { case 0 => [] } )
hardHelper( a, n + 1 ) ≡
  let t = a[n + 1].length
  and ( k, f ) = hardHelper( a, n )
  and k' = k * ( t - 1 )
  and f'( i ) =
        if ( i < k' )
        then easyInduction( f, 1 )( a, n + 1, i )
        else if ( k' <= i < k' + k )
        then easyInduction( f, 1 )( a[ 0..n ] ++ [ [ null ] ], n + 1, i - k' )
        else easyInduction( ( b, m, j ) => f( b, m, j + k ), 0 )( a, n + 1, i - k' - k )
   in ( k', f' )