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);
}
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:
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' )