# 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.