# Efficient method to find a pair that sum to a given value in a list in matematica style

Given an array nums and an number target, find all pairs in array whose sum is equal to target.

A simple method is to generate all possible pairs and compare the sum of every pairs with target,

obviously, this is an inefficient method

SeedRandom[1];
nums = Union@Round[RandomReal[20, 10^3], 0.001];
target = 5;

Select[Subsets[nums, {2}], Total[#] == target  &] // AbsoluteTiming


{0.846554, {{0.362, 4.638}, {0.671, 4.329}, {1.402, 3.598}, {1.561, 3.439}}}

A better way is to use a hash table

dict = Association@Table[nums[[i]] -> i, {i, Length@nums}];
Do[With[{n = nums[[i]]},
If[KeyExistsQ[dict, target - n] && n < target - n,
Print[{n, target - n}]]], {i, Length@nums}]


I want to know if there is a more concise and efficient way to do it in Mathematica.

The above data is just for the convenience of testing, the real data has 16-bit machine accuracy,

What I really care about is not just the sum of two numbers, it can also be other binary operations,

For example, the ratio of two numbers is close to 2.

target = 1/2;
error = 10^-10.;
Select[Subsets[nums, {2}], Abs[Divide @@ # - target] < error &] // AbsoluteTiming


{0.480564,{{0.342,0.684},{0.469,0.938},{0.671,1.342},{0.914,1.828},{1.104,2.208},{1.12,2.24},{1.335,2.67},{1.993,3.986},{2.564,5.128},{2.642,5.284},{2.852,5.704},{3.372,6.744},{4.161,8.322},{4.565,9.13},{4.903,9.806},{4.921,9.842},{5.349,10.698},{6.011,12.022},{6.286,12.572},{6.446,12.892},{6.507,13.014},{7.2,14.4},{7.662,15.324},{8.828,17.656},{8.853,17.706},{8.975,17.95},{9.147,18.294}}}

So I hope there is a more general way.

Updated

For summation, I have thought of a good way

GatherBy[nums, Sort@Round[{#, target - #}, 10^-10.] &] //
Select[Length@# > 1 &] // AbsoluteTiming


For the ratio of two numbers, I have no ideas yet.

• If array consists only positive numbers, then you can first eliminate numbers that are greater than target. Mar 11, 2021 at 5:52
• For division, I would suggest to sort the list first and split it into two: the first list negnums contains only negative numbers, the second posnums only positive numbers. Then one can employ a similar strategy as for summation to each of the three pairs {posnums, posnums}, {negnums, posnums}, and {negnums, negnums}. Mar 11, 2021 at 9:05

This might not be perfect "Mathematica style" because it uses Compile and procedural programming. But it is the fastest that I have managed to come up with so far:

cf = Compile[{{nums, _Real, 1}, {target, _Real}, {tol0, _Real}},
Block[{bag, counter, a, x, y, j, tol},
tol = Ramp[tol0];
bag = InternalBag[Most[{0.}]];
a = Sort[nums];
j = Length[a];
y = CompileGetElement[a, j];
Do[
x = CompileGetElement[a, i];
While[j >= i && x + y > target + 0.5 tol,
y = CompileGetElement[a, --j];
];
While[j >= i && Abs[x + y - target] <= tol,
InternalStuffBag[bag, x];
InternalStuffBag[bag, y];
y = CompileGetElement[a, --j];
];
, {i, 1, Length[a]}];
Partition[InternalBagPart[bag, All], 2]
],
CompilationTarget -> "C",
RuntimeOptions -> "Speed"
];


Now:

pairs = cf[nums, target, 1. 10^-8]; // RepeatedTiming


7.78*10^-6

The complexity is dominated by the Sort and depends on which sorting algorithm is employed. For example, a quicksort would use $$O(n \, \log(n))$$ time on average where $$n$$ is the length of the list num. The rest of the algorithm (the Do loop) has complexity $$O(n)$$

• Really fast, +1, I tried to modify the code, but it doesn’t seem to work for division. Mar 12, 2021 at 8:19
• Well, that was not part of your question when I wrote the above... Mar 12, 2021 at 9:46

IntegerPartitions is very fast but only works with rational numbers, so we need to round to $$1/1000$$ instead of $$0.001$$:

SeedRandom[1];
nums = Union@Round[RandomReal[20, 10^3], 1/1000];
target = 5;

IntegerPartitions[target, {2}, nums] // AbsoluteTiming
(*    {0.004219, {{2319/500, 181/500}, {4329/1000, 671/1000},
{1799/500, 701/500}, {3439/1000, 1561/1000}}}    *)


As for comparing the ratio of two numbers, you can extend the above to using the rounded logarithms of the numbers.