2-dimensional ranking of multiple arrays


Given a constant dimension $ d$ , say $ d=2$ we want the following:

Input: $ A_1\ldots A_m$ : $ m$ arrays of length $ n$ of integers

Each input array $ A_i$ must be a permutation of the numbers $ 1..n$ , so in each array each number from $ 1$ to $ n$ appears exactly once.

Output: For each pair (in the case $ d=2$ ; triplets in the case of $ d=3$ etc.) of numbers $ (1,1),(1,2)\dots(n,n)$ , we want a count for in how many input arrays the first number of the pair is also the first to appear in the array (among the numbers of that pair).

Question: Can this be done quicker than $ O(mn^d)$ in the worst case?

Upper and lower bounds

The output is represented as a $ d$ -dimensional array of length $ n$ . Therefore a lower bound for the runtime complexity is $ O(n^d)$ .

The naive approach is to create $ m$ mappings from each number to its index for each input array. Then for all $ n^d$ tuples, walk through the $ m$ mappings, yielding a runtime complexity upper bound of $ O(dmn^d)$ and since $ d$ is a constant this is $ O(mn^d)$ .

Examples

A = (1,2,3,4),        Output =  1 2 3 4     (1,2,3,4),                  -------     (1,2,3,4),     =>       1 | 4 4 4 4     (1,2,3,4)               2 | 0 4 4 4                             3 | 0 0 4 4     d=2, m=4, n=4           4 | 0 0 0 4  =======================================  A = (4,3,2,1),         Output = 1 2 3 4     (1,2,3,4),                  -------     (1,2,3,4)      =>       1 | 3 2 2 2                             2 | 1 3 2 2     d=2, m=3, n=4           3 | 1 1 3 2                             4 | 1 1 1 3 

Application

While writing poker analysis software, I’m particularly interested in the case $ d=3, m\approx 1250, n\approx 1250$ . I estimate that the naive $ O(mn^d)$ solution takes multiple hours but less than a day when using native Java arrays (no hashmaps etc) on a single thread.