Given a fixed 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 tuple (pairs in the case $d=2$; triplets in the case of $d=3$ etc. In this example we'll use pairs) of numbers $(1,1),(1,2)\dots(n,n)$, we want a count for in how many input arrays the first number of the tuple is also the first to appear in the array (among the numbers of that tuple). The order in which the other numbers of the tuple appear in an array doesn't matter, as long as they come later than the first number of the tuple.
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)$.
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
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.
$d$ stands for the number of players that are still active during a poker hand. Normal poker software handles the case $d=2$. Some high-end software handles the case $d=3$.
I'm interested in the case $d=2$, but then the naive approach is already quick enough in most situations. I'm mainly interested in the case $d=3$. I'm less (but still) interested in the case $d=4$ which is probably unfeasible and even less interested in greater values. I'm not interested in $d>10$. A poker table has 10 players max. The values of $m$ and $n$ do not increase/decrease with $d$.