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

Question

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.

Henrik Schumacher · Accepted Answer

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

Roman · Answer

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.

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

2 Answers

Add your own answers!

Ask a Question