10
$\begingroup$

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.

Additional

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.

$\endgroup$
2
  • $\begingroup$ If array consists only positive numbers, then you can first eliminate numbers that are greater than target. $\endgroup$ Mar 11, 2021 at 5:52
  • $\begingroup$ 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}. $\endgroup$ Mar 11, 2021 at 9:05

2 Answers 2

8
$\begingroup$

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 = Internal`Bag[Most[{0.}]];
    a = Sort[nums];
    j = Length[a];
    y = Compile`GetElement[a, j];
    Do[
     x = Compile`GetElement[a, i];
     While[j >= i && x + y > target + 0.5 tol,
      y = Compile`GetElement[a, --j];
      ];
     While[j >= i && Abs[x + y - target] <= tol,
      Internal`StuffBag[bag, x];
      Internal`StuffBag[bag, y];
      y = Compile`GetElement[a, --j];
      ];
     , {i, 1, Length[a]}];
    Partition[Internal`BagPart[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)$

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

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.

$\endgroup$

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.