9
$\begingroup$

Suppose that sequence $A$ contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ and sequence $B$ contains $m$ integers $b_1,b_2,b_3,\ldots,b_m$. We know that $m \geq n$. We assume without loss of generality that both sequences $A$ and $B$ are sorted in ascending order.

What's the fastest algorithm to determine if there exists an integer $k$ such that the sequence $a_1+k,a_2+k,a_3+k,\ldots,a_n+k$ is a subsequence of the sequence $B$?

Here is a naive algorithm, which would take $O(n(m-n))$ time. Store the sequence $B$ as a hashtable. For each element $b_j$ of the $B$ (except the largest $n$ elements), use $b_j-a_1$ as your guess at $k$; you can verify this guess by checking whether each of $a_1+k,\dots,a_n+k$ are in the hashtable $B$. This takes $O(n)$ expected time per guess at $k$, and you make $m-n$ guesses, so in total the expected running time is $O(n(m-n))$. Can we do better?

I came across this problem while trying to match two binary images (testing whether one image contains the other).

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. Please post further ideas for algorithms in the chat room, and reserve comments for requests for clarification, suggestions about how to improve the question, etc. Thank you! $\endgroup$ – D.W. Nov 28 '19 at 18:22
3
$\begingroup$

Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space.

Initialize a hashtable of counts $C$ to all zeros. Then, repeat $t$ times: randomly pick $i,j$, compute $b_j-a_i$, and increment $C[b_j-a_i]$. Finally, sort $C$ by counts, from largest count to smallest; then for each of the largest few values of $C[k']$, try $k'$ as your guess at $k$, and verify each guess.

Notice that in each iteration, the probability of incrementing $C[k]$ is at least $1/m$; whereas if $l\ne k$, we expect $C[l]$ to be incremented much more rarely (assuming the integers in the arrays are random and large enough). Thus, after $t$ iterations, we expect $\mathbb{E}[C[k]] \ge t/m$ but $\mathbb{E}[C[l]] \ll t/m$. So, once $t$ is large enough, $C[k]$ should be larger than every other entry in $C$.

How large does $t$ need to be? I expect that $t = O(m \log m)$ should suffice, based on a central limit theorem approximation for the counts $C[l]$, assuming we are willing to accept a small probability of error (which can be driven exponentially small). The constant factor hidden by the big-O notation might be non-trivial.

This is only a heuristic, and there will certainly be inputs where it fails.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I made some mistakes too ,what i want to say is , you should have sorted the two arrays first ,don't just pick bj - ai randomly ,when bj is too large and ai too small ,that kind of pick makes no sense at all (defintely won't hit k),then it should be 1/(m-n) ,which is more optimal . $\endgroup$ – iouvxz Nov 27 '19 at 20:32
  • $\begingroup$ well don't just SORT them ,sort the first array ,then sort the largest n elements and smallest n elements of b array, the middle m-2n elements don't need to be sorted .this operation is O(nlog(n)+m) $\endgroup$ – iouvxz Nov 27 '19 at 20:37
  • $\begingroup$ This algorithm won't perform well when array2 contains a lot of consecutive integers which cannot be eliminated from possibility . $\endgroup$ – iouvxz Nov 27 '19 at 21:09
  • $\begingroup$ @iouvxz, I don't immediately see why it would perform poorly in that case. My algorithm does not eliminate anything from possibility, so I'm not sure what you're referring to. In any case, as I wrote, the heuristic is designed for the case where the other elements of array $b$ are randomly chosen from a large range. Randomly chosen elements are unlikely to be consecutive. As far as your proposed variants on my algorithm, those are your variants, and you are free to try them if you like, but they're not what I am recommending. $\endgroup$ – D.W. Nov 27 '19 at 21:41
  • $\begingroup$ Your first question , a full match can be called a k match ,a match with only one miss can be call a k-1 match ,etc .If array b contains a lot of consecutive integers ,then there would be a lot of k-1 match , k-2 match ,k-i match ,every pick has a 1/(n-m) *(1 - i/k) chance for these correspond slots to increase by 1 .Then it's hard for C[k] to be larger than all of it ,or even most of it . $\endgroup$ – iouvxz Nov 27 '19 at 21:50
0
$\begingroup$

Here is an algorithm running in $\mathcal{O}(n\sqrt{n} + m\log m)$ time.

Let $w$ denote the function that for integer $t$, counts the number of pairs that their difference is $t$: $w(t)=\lvert\{(x,y): x\in A, y\in B, y-x=t\}\rvert$. If we had access to $w(t)$ we could simply find its maximum and see if it's $n$ or not. The main idea is to estimate $w$ using the Fast Fourier transform. If the numbers are bounded it will produce the exact solution, otherwise, one can use modulus to a sufficiently big number and then verify the solutions once they're found.

Let $N,M$ be integers (to be defined later), and $u,v\in \mathbb{R}^N$ be vectors defined as $$u[i] = \lvert\{x\in A\colon M-x\equiv i \pmod N \}\rvert$$ $$v[i] = \lvert\{y\in B\colon M+y\equiv i \pmod N \}\rvert$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is $k$ such that $$\forall x\in A \exists y\in B: y-x=k,$$ then we can conclude $$ w[k \bmod N]=\sum_{i: v[i]\neq 0} v[i] u[i-k \bmod N]= n$$ which by construction is the maximum value that $w$ can attain. Therefore, we only need check if $\max_i w(i)=n$ or not. Then, we verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $\mathcal{O}(N \log N)$ time, and then finding the maximum element and verifying it takes $n$ steps, so overall $\mathcal{O}(N \log N)$ time and space.

If the numbers in both sets are bounded by $N$ this is an exact solution. But if you pick $N$ too small, $w(i)=n$ can happen because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$; there might be several of them, but their number can be bounded. To have $\ell$ such indices, one must have at least $1+2+\dots + \ell$ collisions, which implies $$P[\lvert\{i\colon w[i]\ge n\}\rvert \ge \ell] \le P[\text{# collisions}\ge (\ell+1)\ell/2].$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number $N$ such that $N>2m$, and pick $M$ uniformly at random from $\{1,\dots,N\}$, the collision probability is bounded by $1/2m$, so by Markov's inequality is $$\le \frac{nm/N}{\ell^2/2}\le \frac{n}{\ell^2}$$ So with probability as close to $1$ as you want, $\ell=\mathcal{O}(\sqrt{n})$. Therefore, the overall time complexity of the algorithm is $$\mathcal{O}(n\sqrt{n} + m\log m)$$ in which $m\log m$ is the FFT and iFFT step (since we set $N=2m$), and $n \sqrt{n}$ is the verification step.

There are two ways I see to improve this:

  1. One can run $\log n$ separate instances of the algorithm without the verification, and take the intersection of maximum indices that $w[i]\ge n$ (after shifting by $M$). If one can show that the number of shared collisions drops by $1/2$ or some other constant every time, this would show a total running time of $\mathcal{O}(m\log^2 m)$.
  2. One can construct a better hashing mechanism for $u$ and $v$ and use higher moments for Markov and make the concentration sharper.

Nevertheless, if you're looking for a practical solution this algorithm could work just fine. For instance, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step as soon as you find a mistake.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Fascinating approach! I think I get the basic idea but I get a bit confused starting with the discussion on collisions. What do you mean by "the collision probability"? What event is that the probability of? What constitutes a collision? Do you mean indices $i,i'$ such that $i\equiv i' \pmod N$? If so, there doesn't seem to be any probability involved; it either has probability 0 or 1, regardless of $M$, and the number of collisions is fixed once you choose $N$ (it isn't random). $\endgroup$ – D.W. Nov 28 '19 at 18:38
  • $\begingroup$ Also, I'm a bit confused by what role $M$ plays. It seems you'll get the same answer from the algorithm regardless of $M$. Can you edit to elaborate on these aspects of the answer? $\endgroup$ – D.W. Nov 28 '19 at 18:38
  • $\begingroup$ "To have ℓ such indices, one must have at least 1+2+⋯+ℓ collisions" ,care to elaborate ? I thought you can have just one collision to make all w(i) > n. $\endgroup$ – iouvxz Nov 28 '19 at 19:12
  • $\begingroup$ by collision I mean when $x-y\neq x'-y'$ but $x-y\equiv x'-y' (\mathrm{mod} N)$, every such incidence is counted as one collision, if there is more than one index $w[i]\ge n$, this can only be explained by several collisions that have been binned into $i$, causing $w[i]$ to go up to $n$, but @D.W. you're right about the role of $M$, the missing piece is that $N$ must be chosen also randomly in the range $[2m,4m]$, I'll update the post to reflect the changes $\endgroup$ – Ameer Jewdaki Nov 28 '19 at 20:23
  • $\begingroup$ array_a=0,1,2,4; array_b=0,1,2,3 ; N=4 ,all w(i)=4 ,there should be 10 collisions ,what are they ? $\endgroup$ – iouvxz Nov 28 '19 at 20:55
0
$\begingroup$

This is a completely different algorithm, which I believe works in $O(m\log m)$ worst case, and should work for integer or real numbers.

Let us assume that $A$ and $B$ are already in ascending order, otherwise spend $O(n\log n+ m\log m)$ to sort them. We slightly strengthen the requirement for algorithm $\mathcal{A}(A, B)$ to return all indices $i$ such that $A$ can be mapped to $B$ with offset $k=b_i-a_1$, meaning that the mapping starts at $b_i$ onwards. The high-level idea is to solve the sub-problems corresponding to a subarray of $A$ and merge the indices in a way that only valid solutions remain.

The recursion, however, depends on how close $A$ is to an arithmetic progression. Formally, let periodicity $\tau(A)$ be defined as: $$\tau(A) = \min \{s\in\mathbb{N}^+: a_{i+s+1}-a_{i+s}= a_{i+1} - a_i \text{ for all valid } i, s\} $$ In words, this means elements of $A$, are periodic with a minimum cycle $\tau(A)$, up to some offset.

Case I ($\tau(A)<n/3):$ Let $s=\tau(A)$ and $\ell = a_s - a_1$. Recursively compute $I=\mathcal{A}(A[1:s],B)$. One observation is that if $i,j\in I$, corresponding to index sets $J_i, J_j$, and $b_j - b_i = \ell$, the index sets $J_i, J_j$ can be concatenated to show $i\in \mathcal{A}(A[1:2s],B)$. This is a simple consequence of $A$ being $s$ periodic, and $b_j = b_i + \ell$ ensures that the index set $J_j$ starts where $J_i$ ends. Let $$R[i] = \lvert\{j \in I\colon j>i, b_j - b_i \text{ divisible by } \ell\}\rvert$$ Then, $R[i]$ can be computed based on $R[i']$ that $i'>i$, and the new index set $I'$, is the indices that $R[i]\ge n/s$. The cost for this step is bounded by $O(m)$.

Case II ($\tau(A)>n/3$): By definition, for $s=n/3$ there should be an index $i$ that $a_{i+1}-a_i \neq a_{i+1+s}-a_{i+s}$. If $i\le n/3$, we will have $i,i+s\le 2n/3$ which certifies that $\tau(A[1:2n/3])>n/3$. Otherwise, $i>n/3$ implies that $\tau(A[n/3:n])>n/3$.

Wlog assume $\tau(A[1:2n/3)>n/3$, and choose the lower half $A'=A[1:n/2]$ to recurse on (otherwise choose the upper half, same arguments would follow). Recursively compute $I=\mathcal{A}(A',B)$. For each index $i\in I$, check if the rest of the sequence can be found in $B$. Since both sequences are sorted this can be done in $O(n)$ step for each index, which implies an overall $O(|I|\cdot n)$ time to compute the valid indices, and return them as $\mathcal{A}(A, B)$. The efficiency of this step relies on the following claim:

Claim: $|I|\le 6m/n$, meaning that solutions are not too much overlapping.

Proof of claim: We show $|I|> 6m/n$ leads to a contradiction. Each index $i\in I$ is the starting point of a set of indices $J_i=\{i=j_1,\dots,j_{n/2}\}\subseteq B$, that map $A'$ to $B$ up to some offset. Collectively, there are at least $3m$ indices: $$\sum_{i\in I} |J_i| = |I|n/2\ge 6m/n \cdot n/2=3m$$ Since $|B|=m$, by pigeonhole principle, there is at least one index $x\in B$ appears in 3 separate solutions: $$\exists x\in B, r,s,p\in I\colon\; x\in J_r\cap J_s\cap J_p$$

Let $s $ be the median of the three $r<s<p$. Since $x\in J_s$, and $|J_s|=n/2$, $x$ partitions $J_s$ to two parts, one of which should have less than $n/4$ indices, which we assume is the lower part: $$J_s=\{j_1=s, j_2, \dots, j_\ell=x\}, \ell\le n/4$$ By construction, $s=j_1$ is mapped to $a_1$, up to $a_\ell$ up to some offset. But we also have $x\in J_p$, this implies a periodict less than $\ell\le n/4$ in $A'$, which contradicts $\tau(A')>n/3$. (there's a few details I will add later)

Overall Complexity At each step of the recursion, we pay $O(m)$. The periodicity $\tau(A)$ can also be computed in $O(n)$, by computing the longest suffix which is also prefix, of $\mathrm{diff}(A)$, that is the increment array $a_2-a_1, \dots, a_n-a_{n-1}$. However, the size of the problem reduces by at least $1/2$ in each recursive step. There will be $\log n$ steps in worst case, which implies the time complexity is bounded by $O(m \log n)$. Adding the sorting costs, and since $m>n$, the overall complexity is bounded by the sorting time $O(m\log m)$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't understand Case I. It introduces $s$ without defining it. Do you mean to use $\tau(A)$ instead of $s$ throughout? Do you really mean to use $n/s$, or perhaps do you mean $\lfloor n/\tau(A) \rfloor \tau(A)$? When you write "this holds", what are you claiming holds? $\endgroup$ – D.W. Nov 30 '19 at 0:46
  • $\begingroup$ Can you elaborate on why $x \in J_p$ implies a periodicity less than $\ell$ in $A'$? $\endgroup$ – D.W. Nov 30 '19 at 0:55
  • $\begingroup$ "...τ(A[1:2n/3])>n/3. Otherwise, i>n/3 implies that τ(A[n/3:n])>n/3." no ,A= set(range(36))-{5,15,26},which is [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35],now n=33 ,τ(A[:])=19,T(A[0:22])=9,T(A[12:34])=10(I'm using python indexing,which translate to A[1:22],A[11:33] in your situation), how do you explain this? $\endgroup$ – iouvxz Nov 30 '19 at 11:04
  • $\begingroup$ Or A= set(range(360))-{50,150,260} ,to eliminate confusions about boundaries .Here, n =357, τ(A[:])=208,τ(A[:238])=99,τ(A[119:])=109 ,n/3 =119. $\endgroup$ – iouvxz Nov 30 '19 at 11:11
  • $\begingroup$ ls = sorted(set(range(360)) - {50, 150, 260}) diff = [i - j for i, j in zip(ls[1:], ls)] def check_period(seq, i): return all(seq[j] == seq[i + j] for j in range(len(seq) - i)) def get_period(seq): return next(i for i in range(1, len(seq)) if check_period(seq, i)) print(get_period(diff[:]), get_period(diff[:119 * 2]), get_period(diff[119:])) # run this in python to check $\endgroup$ – iouvxz Nov 30 '19 at 11:43

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.