10
$\begingroup$

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)$.

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.

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

$\endgroup$
1
  • $\begingroup$ We can, by sorting the input arrays lexicographically and bundling up operations, add factors $\frac nm, \frac { n^2 }m,...,\frac{n^n}{m}$. Since $n\approx m$ in your case though, this won't improve the running time $\endgroup$ – Sudix Sep 17 '20 at 12:14
4
+150
$\begingroup$

Here is a solution quite simple to implement, that only improves the $d$ factor.

For the increasing series $[1, 2, .., n]$, get the tuple list of the coordinates to increase in your output array. For $d = 2$ and $n = 4$, this is $H=[(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)]$. Asymptotically (not exactly due to $(a, a)$ being always valid), there are $O(\frac{n^d}{d})$ terms in this list.

Initialize an output array $B$ of size $n^d$ to zeros.

Then, for each of the $m$ arrays $A$ and for each tuple $(a_0, a_1, ..., a_d)\in H$, increase $B[A[a_0], A[a_1], ..., A[a_d]]]$ by 1.

It achieves $O(\frac{m n^d}{d})$.

EDIT

For $d=3$, basically, both tuples $(0, 1, 2)$ and $(0, 2, 1)$ are in the coordinates list to increase. But if you want to use the knowledge that $B[a, b, c] = B[a, c, b]$, you have to keep only tuples non-decreasing after the 2nd integer. So here you leave $(0, 2, 1)$. Be careful to still keep $(a, b, b)$ tuples like $(0, 2, 2)$.

Then you will divide the number of terms in the list by about a factor $2(d-1)!$ for the general case).

At the very end, you have to add a $O(n^d)$ step to gather counts on $B[a, b, c]$ and $B[a, c, b]$. For every tuple $(a, b, c)$ with $b < c$,

  • $S = B[a, b, c] + B[a, c, b]$
  • $B[a, b, c] = S$
  • $B[a, c, b] = S$

This runs in $O(\frac{m n^d}{d!})$.

$\endgroup$
8
  • 1
    $\begingroup$ @Optidad Well, as you said, if $T$ is the output table as per OP's algorithm, then for all permutations $\sigma\in S_{d-1}$, we have $T(x_1,x_2,...,x_d) = T(x_1,x_{\sigma_1},...,x_{\sigma_{d-1}})$, so we can remove all those function inputs that give us no extra information. To input an abitrary vector in this reduced function, we then have to first use the mapping $(x_1,...,x_d)\mapsto (x_1,\text{set_of}(x_2,...,x_d))$. Definition for aboves notation: $$\binom{\{1,...,n\}\setminus\{x\}}{d-1}) := \{S\subseteq\{1,...,n\}\setminus\{x\}:|S| = d-1 \}$$ $\endgroup$ – Sudix Sep 17 '20 at 11:39
  • $\begingroup$ @Sudix Okay I understood, and indeed this can be applied for both input and output. It saves thus the additional gathering step. Even if there is no direct gain in time, it saves a lot of space. $\endgroup$ – Optidad Sep 17 '20 at 13:36
  • $\begingroup$ @AlbertHendriks: You should mention better algorithms you already know about in your question to avoid wasting people's time. I don't see how an algorithm asymptotically faster than $O(mn^d)$ is possible, since looking at the first $m-1$ arrays tells you nothing about the $m$th, suggesting they will need to be processed independently somehow, meaning you would need $o(n^d)$ time per input array. But this cannot be achieved for a 1-array input because the output size is $\Theta(n^d)$. $\endgroup$ – j_random_hacker Sep 17 '20 at 22:46
  • $\begingroup$ The equivalence of 1, 2, 3 and 1, 3, 2 is the less important improvement shown here. Iterating over tuples in each input array separately and directly incrementing counts is clearly a better algorithm than building mappings in an initial pass, since it both avoids the space overhead for storing the mappings and drops the constant factor from $d$ to a factor $\le 1$ that decreases as $d$ increases -- and this speedup was true of the algorithm described in version 1 of the answer (although the speedup claimed at that time was too strong). $\endgroup$ – j_random_hacker Sep 18 '20 at 1:17
  • $\begingroup$ @j_random_hacker Exactly, and luckily that came to light because of the discussions and edits. But now I think these comments are only distracting, so I suggest we remove most or all of them. $\endgroup$ – Albert Hendriks Sep 18 '20 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.