4
$\begingroup$

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will run in $L^3$ time.

Can I do any better?

$\endgroup$
  • $\begingroup$ What kind of numbers? It is probably easy if you consider $\mathbb{Z}/2$, but possibly harder with complex numbers in $\mathbb{C}$. $\endgroup$ – babou Aug 5 '14 at 16:37
  • $\begingroup$ @babou integers or integers mod p. $\endgroup$ – john mangual Aug 5 '14 at 16:46
  • 5
    $\begingroup$ Let $max(L) = m$, I believe you can use FFT for a runtime of $\mathcal{O}(m \log{m} + n)$. See: stackoverflow.com/questions/1560523/… $\endgroup$ – Michael Xu Aug 5 '14 at 20:07
  • $\begingroup$ How many triples, which satisfy the condition $a + c = 2b$, are in the list $(0, 0)$? It seems to me, 8 $\endgroup$ – HEKTO Aug 6 '14 at 18:48
  • $\begingroup$ @MichaelXu I notice it uses a bitmask rather than the list of number itself, which is fine. The FFT approach shoudl be related to Roth's theorem in mathematics, counting arithmetic progressions like these. $\endgroup$ – john mangual Aug 6 '14 at 19:04
3
$\begingroup$

Given that the OP is rather unprecise as to the kind of numbers he is considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to limit the number of assumptions I can make. And while I am at it anyway, I will generalize a bit.

This builds on the contributions of previous answer and comments, by Rick Decker, Hendrik Jan. and HEKTO.

Generalized statement of the problem

We consider four sets of values $\mathcal{U}, \mathcal{V}, \mathcal{W}, \mathcal{Z}$, two functions $f:\mathcal{U}\times \mathcal{V}\to \mathcal{Z}$ and $g:\mathcal{W}\to\mathcal{Z}$. Given 3 sets or lists of values $U,V,W$, respectively from $\mathcal{U}, \mathcal{V}, \mathcal{W}$, count the number of triples $(u,v,w)\in U\times V\times W$ such that $f(u,v)=g(w)$. Each computation of the functions $f$ and $g$ is supposed to be in constant time.

Let $n=max(|U|,|V|,|W|)$

General solution

This is essentially HEKTO's suggestion.

Build a hash table containing each value $w\in W$ indexed by $g(w)$. This has a cost $O(n)$ under the Simple Uniform Hashing Assumption(SUHA). Without the SUHA, one can use a balanced tree with complexity $O(n\log n)$.

Then for each $u\in U$ and for each $v\in V$ check whether $f(u,v)$ is in the hash table in constant time (or in the balanced tree in logarithmic time). If it is in an entry $g(w)$, then add $(u,v,w)$ to the list of solutions (or increase the solution count by one).

Complexity is $O(n^2)$ with hash table, under SUHA, or $O(n^2\log n)$ with a balanced tree.

Case of ordered sets

This is essentially Hendrik Jan's suggestion.

We assume that one of the two sets $\mathcal{U}$ or $\mathcal{V}$ (say $\mathcal{V}$, w.l.o.g.) and the set $\mathcal{Z}$ are totally ordered and that the function $f$ is monotonic with respect to the argument in the ordered set (here the second argument).

Then we can have a modified algorithm that does not need a hash table.

First sort the set $V$.

Build a list $L$ of pairs $(w,g(w))$ for all $w\in W$, sorted with respect to the second element.

Then for each $u\in U$, compare the ordered values of $f(u,v)$ with the ordered values $g(w)$ of the pairs in $L$, by moving up the two list $V$ and $L$ as you would do for set intersection, and add the answer $(u,v,w)$ whenever $f(u,v)=g(w)$ for some pair $(w,g(w))$.

Complexity is $O(n^2)$.

Application to "numbers" and arithmetic progression

We consider the initial problem of detecting arithmetic progressions in the elements of a list.

The three lists of the abstract case are the same list. The function $f$ is addition, and the function $g$ is doubling (i.e. product by 2).

The ordered set solution applies well to integers, rationals, or reals (with some care).

Complex numbers are not an ordered field. However they can be considered as an ordered groups with respect to addition, by prioritizing coordinates, so that $a+ib> a'+ib'$ iff $a>a' \vee (a=a' \wedge b>b')$. So the ordered set construction can be used.

The hash table algorithm seems necessary in the case of $\mathbb{Z}/p$ (i.e. integers modulo $P$) since non-trivial linearly ordered groups are necessarily infinite, which is not the case for $\mathbb{Z}/p$.

However the ordered set construction could be adapted to $\mathbb{Z}/p$ without loss in complexity, by allowing the list $L$ to be scanned twice, with some proper bookkeeping.

$\endgroup$
  • $\begingroup$ I don't understand why your General Solution is O(n^2). The checking in hashtable is O(n), this should be O(n^3). The solution for case of ordered sets is very well explained. $\endgroup$ – InformedA Aug 6 '14 at 6:08
  • 1
    $\begingroup$ @randomA You are correct in the sense that my answer was not precise enough. This is true only under the Simple Uniform Hashing Assumption (SHUA). Though often used, this is not a totally inoccuous assumption, and I should have been more careful. This a bit glossed over in a text on hash tables I had just looked at. I will amend the answer accordingly, as soon as I finish some minor changes I was preparing. Thanks. - - - - I did not much like the H-table anyway. $\endgroup$ – babou Aug 6 '14 at 8:10
  • $\begingroup$ @randomA Actually, I think it is not the hash table check in constant-time that you should criticize, as much as my assertion that the hash table building is in linear time. If the checking is not in constant time, then building the table cannot be linear. $\endgroup$ – babou Aug 6 '14 at 8:56
  • $\begingroup$ you are right, that one as well $\endgroup$ – InformedA Aug 6 '14 at 9:10
  • $\begingroup$ @randomA Modified. Is it clear? $\endgroup$ – babou Aug 6 '14 at 9:39
2
$\begingroup$

An often-useful technique is to sort the list first. Then, starting with the smallest element, $x_1$, consider pairing $x_1$ with $x_2$. For them to be the first two terms in an arithmetic sequence, you'll need to have an $x_i = (x_2-x_1)+x_2$. You can find such an element by, say, a binary search. If that fails, look at the pair $x_1, x_3$ and do the same thing. Once you've exhausted the pairs starting at $x_1$, look at the pairs $x_2, x_3$, then $x_2, x_4$ and continue, counting the successes.

The sorting will take $O(n\log n)$ steps. You'll have to check $O(n^2)$ pairs and for each do a binary search for the third element, for a total of $O(n\log n+n^2\log n)$ steps.

There are some improvements you can make to this algorithm, but this should get you started.

$\endgroup$
  • 1
    $\begingroup$ Avoid the binary search. Sort the list. For each fixed $x_1=a$ let $x_3=c$ run over the list, and check whether $x_1=x_3$ equals $2x_2=2b$ for some element $x_2$ in the list by moving $x_2$ over the list together with $x_2$. $O(n^2)$. $\endgroup$ – Hendrik Jan Aug 5 '14 at 14:30
  • $\begingroup$ @HendrikJan - no need to move the $x_2$. We can create a hash table from the original list and verify that $(x_1 + x_3) / 2$ is in the table in $O(1)$ time $\endgroup$ – HEKTO Aug 5 '14 at 15:25
  • $\begingroup$ I do not see that using a hash table will improve the complexity, but it might hurt the efficiency (more complex code). However, for numbers that cannot be sorted, you can apply @HendrikJan 's method to the list in any order, and have the list of doubles $2b$ in a hash table for checking. This can be abstracted to apply to lots of data with whatever weird operator you wish to use. $\endgroup$ – babou Aug 5 '14 at 17:06
2
$\begingroup$

Sort the list increasingly, in time $O(n\log(n))$.

For every $j$, consider the two sequences formed by the left-differences $L[j]-L[j-1], L[j]-L[j-2],L[j]-L[j-3]...$ and the right-differences $L[j+1]-L[j],L[j+2]-L[j],L[j+3]-L[j]...$

By a simple list merging process, you will detect all equal values in the two lists, corresponding to arithmetic triples, using no more than $\min(j,n-j)$ comparisons.

Repeating for all $j$, you count all arithmetic triples in time $\Theta(n^2)$.

# Input (presorted)
L= [ 1, 2, 3, 6, 7, 9, 11 ]; n= len(L)

# Try all middle elements
for j in range(1, n - 1):
    # Detect all arithmetic triples by merging the left and right lists
    i= j - 1; k= j + 1
    while 0 <= i and k < n:
        if L[j] - L[i] < L[k] - L[j]:
            # Advance in the left list
            i-= 1
        elif L[j] - L[i] > L[k] - L[j]:
            # Advance in the right list
            k+= 1
        else:
            # Report a triple and advance in both lists
            print L[i], L[j], L[k]; i-= 1; k+= 1

Output:

1 2 3
3 6 9
1 6 11
3 7 11
7 9 11

This is worst-case optimal, as a perfect arithmetic sequence has $\Omega(n^2)$ arithmetic triples. Constant extra space.

A much harder challenge is to find an output-sensitive solution (when the number of arithmetic triples is $o(n^2)$).

$\endgroup$
  • $\begingroup$ Before you learn it the hard way: after 10 edits, your contribution automatically becomes community wiki. And you no longer get rep for the upvotes. So avoid minor edits, or save them for later. $\endgroup$ – babou Aug 5 '14 at 20:30
  • $\begingroup$ Thanks for the tip. Usually I can't help it: proofreading and proofreading again. $\endgroup$ – Yves Daoust Aug 5 '14 at 20:31
  • 1
    $\begingroup$ It definitely does not! We like well-prepared posts, but we also like improvements, of course. This has been discussed/explained on Computer Science Meta before (1, 2). However, many (insignificant) edits are troublesome because it keeps bumping the thread. Find some recommendations on preparing posts here. (cc @babou) Good to have another user on board who cares about quality! $\endgroup$ – Raphael Aug 6 '14 at 10:19
  • 1
    $\begingroup$ @babou Well, I agree that preventing small polishing is not ideal, but given how the platform works it can't be helped. There are many discussions on Meta Stack Exchange on this, including proposals to just not bump minor edits to the main page, but no one knows how to reliably detect such edits. So, as you say, we'll have to live with the limitations reality puts on our ideals. $\endgroup$ – Raphael Aug 6 '14 at 11:05
  • 1
    $\begingroup$ @babou That is to be expected. The proper response is to improve the question (which I'd assume would be necessary), comment, vote for reopening and maybe take it to Computer Science Meta. Anyway, if you want to continue discussing these things, please do so in Computer Science Chat; this is not the right place. $\endgroup$ – Raphael Aug 6 '14 at 13:34

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.