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.