The most efficient algorithm to find all possible integer pairs which sum to a given integerWhat algorithm and tools should I use to search a data set for the point nearest to a given point?How do I find the all valid pairings between two sets?All possible pairs of two itemsEfficient way to sum all the primes below $N$ million in MathematicaGiven a list of triangle vertices, how to find the neighbors for each vertex?Find random $n$ combinations of values with a given sumHow to efficiently find all combinations of the letters in an alphabet given a conditionWhat is the algorithm to find the Up-sets of this set?How can I find the the greatest common divisor with Euclid's algorithm?How to find all prime power factorizations of an integer
Can one define wavefronts for waves travelling on a stretched string?
Proof of Lemma: Every integer can be written as a product of primes
Latex for-and in equation
Why isn't KTEX's runway designation 10/28 instead of 9/27?
Pronouncing Homer as in modern Greek
Are Warlocks Arcane or Divine?
I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?
The One-Electron Universe postulate is true - what simple change can I make to change the whole universe?
Why is delta-v is the most useful quantity for planning space travel?
Fast sudoku solver
Why are all the doors on Ferenginar (the Ferengi home world) far shorter than the average Ferengi?
What's an appropriate phrasing of a caveat about self-citation?
Is the next prime number always the next number divisible by the current prime number, except for any numbers previously divisible by primes?
Can I Retrieve Email Addresses from BCC?
How to be able to process a large JSON response?
node command while defining a coordinate in TikZ
Stereotypical names
Why are on-board computers allowed to change controls without notifying the pilots?
Music terminology - why are seven letters used to name scale tones
What is the opposite of 'gravitas'?
In Star Trek IV, why did the Bounty go back to a time when whales were already rare?
You're three for three
Bob has never been a M before
Adding empty element to declared container without declaring type of element
The most efficient algorithm to find all possible integer pairs which sum to a given integer
What algorithm and tools should I use to search a data set for the point nearest to a given point?How do I find the all valid pairings between two sets?All possible pairs of two itemsEfficient way to sum all the primes below $N$ million in MathematicaGiven a list of triangle vertices, how to find the neighbors for each vertex?Find random $n$ combinations of values with a given sumHow to efficiently find all combinations of the letters in an alphabet given a conditionWhat is the algorithm to find the Up-sets of this set?How can I find the the greatest common divisor with Euclid's algorithm?How to find all prime power factorizations of an integer
2
$begingroup$
I wrote a module in Mathematica which finds all possible pairs of integers from a specified list of integers (which can be negative, zero, or positive) which sum to a specified integer m.
The only limiting assumption this algorithm has is that the user only wishes to get the set of all unique sums which sum to m.
Is there a faster algorithm to do this? I've read that making a Hash table is of complexity O(n). Is my code of time O(n)? If it of time O(n), is it a Hash table, or is it something else? If it is not of time O(n), how efficient is it?
FindTwoIntegersWhoseSumIsM[listOfIntegers_,m_]:=Module[
i,distanceFrom1ToMin,negativeFactor,distance,start,finish,(*Integers*)
sortedList,numberLine,temp,finalList,(*Lists*)
execute(*Boolean*)
,
(*There are possible inputted values of m with a give integer set input which
make the execution of this algorithm unnecessary.*)
execute=True;
sortedList=Sort[DeleteDuplicates[listOfIntegers]];
(*Create a continuous list of integers whose smallest and largest entries is equal
to the smallest and largest entries of the inputted list of integers, respectively.*)
(*Let this list be named numberline.*)
(*:::::Construction of numberline BEGINS::::*)
(*If the listOfIntegers only contains negative integers and possibly zero,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]<=0),
(*If m is positive, there is no reason to proceed.*)
If[m>0,execute=False,
(*If m [Equal] 0 then if two or more zeros are in listOfIntegers, they should be outputted to the user.
Therefore, we write m>0 instead of m[GreaterEqual]0 in the conditional above.*)
(*Otherwise, treat it as if all integers were positive with a few considerations.*)
negativeFactor=-1;
sortedList=Reverse[-sortedList];
If[sortedList[[1]]!=0,
numberLine=Range[sortedList[[Length[sortedList]]]]
,
numberLine=Join[0,Range[sortedList[[Length[sortedList]]]]]
]
]
,
negativeFactor=1;
(*Else If the integer set contains negative and positive integers,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]>0),
numberLine=
Join[
-Range[Abs[sortedList[[1]]],0,-1](*negative integer subset*)
,
Range[sortedList[[Length[sortedList]]]](*positive integer subset*)
]
,(*Else if the integer set contains only whole numbers,*)
If[(sortedList[[1]]==0)&&(sortedList[[Length[sortedList]]]>0),
(*If the list of integers are all positive and m is negative,
there is no reason to proceed.*)
If[m<0,execute=False,(*Otherwise,*)
numberLine=
Join[
0(*zero*)
,
Range[sortedList[[Length[sortedList]]]](*positive integers*)
]
]
,(*Else if the integer set contains only the natural numbers.*)
(*If the list of integers are all positive and m is negative or zero,
there is no reason to proceed.*)
If[m<=0,execute=False,numberLine=Range[Max[sortedList](*positive integers*)]]
]
]
];
(*:::::Construction of numberline ENDS::::*)
(*Print[numberLine];*)
If[execute==False,finalList=$Failed,
(*Mark all numbers which are in numberline but are not in listOfIntegers with a period.
Sort[] will still sort this list of mixed precision of numbers in ascending order.*)
temp=Sort[Join[Complement[numberLine,sortedList]//N,sortedList]];
(*The main idea of the algorithm is to find the point on numberline to begin selecting two number
combinations which sum to m. m is obviously going to be used when that time comes.
Once that point is selected, integers symmetrically equally distant apart from each other
on both sides of this point (number) in numberline are candidates which sum to m.
To avoid going "out of bounds" of numberline (from either attempting to select a value smaller
than the minimum value of numberline or attempting to select a larger value than the maximum
value of numberline, the following is the maximum distance we can use to obtain ALL possible
two integer combinations which sum to m but of which also prevents us from going "out of bounds".)
*)
(*If the numberline we are about to create had a consistent minimum value of 1
then it would not be offset as it is in general.
The following takes this "offset" into account.*)
distanceFrom1ToMin=Abs[1-Min[sortedList]];
distance=
Min[
distanceFrom1ToMin+Floor[negativeFactor*m/2]
,
Length[temp]-(distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1)
];
start=distanceFrom1ToMin+Floor[negativeFactor*m/2]+1;
finish=distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1;
(*With the bound distance established, we are ready to begin selecting numbers from numberline.*)
finalList=;
i=1;
While[i<=distance,
finalList=Append[finalList,temp[[start-i]],temp[[finish+i]]];
i++
];
(*It turns out that for even m the first selected integer combination considered is m/2,m/2.*)
If[(Mod[m,2]==0)&&(MemberQ[finalList,negativeFactor*m/2,negativeFactor*m/2]==True),
(*Should there not be two of m/2 in listOfIntegers, we omit this selected combination.*)
If[Length[Flatten[Position[listOfIntegers,negativeFactor*m/2]]]<2,
finalList=Delete[finalList,Position[finalList,negativeFactor*m/2,negativeFactor*m/2][[1]][[1]]]
]
];
(*We selected all possible number combinations in numberline. However, unless listOfIntegers
is all consecutive integers, we need to omit any selected number combination in which either
of the numbers has a "." to the right of it.*)
finalList=negativeFactor*Sort[Select[finalList,Precision[#]==[Infinity]&]]
];
finalList
]
I did the following tests with the code and got these results. (The first number in the time in second it took to do the computation. But you can of course copy the code and do tests yourself.) I omitted most of the results from the last test because it made my post too large, but you will see that it did the computation in 0.209207 seconds.
As the comments in my algorithm (and the algorithm itself suggests), I broke up the number line into negative integers, zero, and the positive integers. I therefore wrote my tests to address all possible situations.
For the positive (non-zero) integer set.
With positive m such that m is larger than what any two number combination in listOfIntegers could possibly sum to.
m = 100; listOfIntegers = RandomSample[Range[20], 6]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
19, 11, 1, 4, 13, 17
0.0371008,
With positive odd m.
m = 215; listOfIntegers = RandomSample[Range[266], 190]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
119, 175, 7, 123, 42, 173, 15, 56, 233, 41, 9, 156, 130, 196, 183,
65, 102, 109, 177, 161, 230, 105, 91, 103, 146, 47, 234, 133, 88, 68,
169, 197, 46, 198, 108, 263, 205, 129, 4, 157, 245, 210, 203, 78,
172, 128, 138, 61, 262, 159, 148, 45, 225, 239, 72, 74, 151, 34, 36,
5, 106, 77, 223, 116, 8, 2, 11, 54, 124, 87, 221, 213, 171, 93, 53,
19, 40, 30, 95, 215, 39, 140, 49, 158, 94, 38, 28, 247, 84, 75, 257,
33, 163, 132, 69, 211, 193, 222, 114, 240, 32, 149, 167, 135, 107,
115, 101, 100, 166, 144, 251, 253, 224, 154, 48, 44, 26, 181, 259,
81, 6, 70, 122, 255, 189, 235, 112, 110, 174, 85, 147, 117, 18, 209,
66, 121, 155, 206, 207, 212, 98, 113, 254, 214, 178, 111, 227, 165,
204, 231, 194, 20, 176, 150, 162, 241, 243, 199, 90, 55, 127, 191,
12, 185, 242, 125, 265, 25, 1, 250, 201, 168, 76, 134, 266, 82, 10,
92, 143, 217, 126, 218, 182, 220, 153, 164, 216, 238, 67, 14
0.136695, 1, 214, 2, 213, 4, 211, 5, 210, 6, 209, 8,
207, 9, 206, 10, 205, 11, 204, 12, 203, 14, 201, 18,
197, 19, 196, 26, 189, 30, 185, 32, 183, 33, 182, 34,
181, 38, 177, 39, 176, 40, 175, 41, 174, 42, 173, 44,
171, 46, 169, 47, 168, 48, 167, 49, 166, 53, 162, 54,
161, 56, 159, 61, 154, 65, 150, 66, 149, 67, 148, 68,
147, 69, 146, 72, 143, 75, 140, 77, 138, 81, 134, 82,
133, 85, 130, 87, 128, 88, 127, 90, 125, 91, 124, 92,
123, 93, 122, 94, 121, 98, 117, 100, 115, 101,
114, 102, 113, 103, 112, 105, 110, 106, 109, 107, 108
With positive even m.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.00998522, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With positive even m such that listOfIntegers contains two of m/2.
m = 22; listOfIntegers = Append[Range[20], 11]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 11
0.00037181, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12, 11, 11
With positive even m such that listOfIntegers contains one m/2.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.000267311, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With any negative m.
m = -6; listOfIntegers = Range[26]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26
0.000108231, $Failed
For the positive integer set (including 0).
With an even m.
m = 88; listOfIntegers = RandomSample[Join[0, Range[122]], 39]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
121, 69, 120, 56, 36, 55, 17, 114, 7, 59, 32, 4, 20, 79, 92, 62, 50,
89, 13, 70, 113, 75, 76, 80, 108, 53, 83, 95, 0, 85, 86, 77, 10, 54,
48, 66, 104, 100, 35
0.000505232, 13, 75, 32, 56, 35, 53
With an odd m.
m = 57; listOfIntegers = RandomSample[Join[0, Range[82]], 52]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
62, 18, 26, 0, 67, 34, 55, 52, 35, 78, 10, 68, 46, 44, 38, 23, 77,
76, 58, 51, 75, 63, 53, 42, 54, 27, 56, 71, 12, 17, 2, 37, 31, 72,
49, 50, 32, 16, 47, 19, 4, 20, 81, 25, 61, 14, 80, 82, 59, 33, 70, 39
0.000372743, 2, 55, 4, 53, 10, 47, 18, 39, 19, 38, 20,
37, 23, 34, 25, 32, 26, 31
For the negative integer set (including 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-2, -16, -15, -9, -5, -12, -8, -22, -7, -21, -13, -18, -4, -11, -10,
-19, -6, -17, -20
0.000105898, $Failed
With a negative odd m.
m = -17; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-5, -1, -10, -13, -15, -19, -2, 0, -7, -18, -3, -21, -8, -11, -12,
-22, -17, -16, -20
0.000640987, 0, -17, -1, -16, -2, -15, -5, -12, -7, -10
With a negative even m.
m = -26; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -16, -11, -14, -17, -13, -1, -9, -15, -20, -18, -4, -21, 0, -8,
-6, -10, -7, -3
0.000329357, -6, -20, -7, -19, -8, -18, -9, -17, -10,
-16, -11, -15
For the negative integer set (excluding 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-20, -7, -16, -21, -11, -13, -5, -2, -6, -19, -1, -12, -18, -14,
-15, -9, -4, -17, -22
0.000102633, $Failed
With a negative odd m.
m = -27; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-18, -17, -22, -13, -1, -11, -19, -8, -16, -6, -21, -12, -20, -3,
-4, -9, -7, -14, -15
0.000242586, -6, -21, -7, -20, -8, -19, -9, -18, -11,
-16, -12, -15, -13, -14
With a negative even m.
m = -26; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -10, -20, -9, -21, -14, -5, -1, -17, -4, -18, -22, -8, -6, -13,
-3, -2, -12, -15
0.000286438, -4, -22, -5, -21, -6, -20, -8, -18, -9, -17,
-12, -14
For the complete integer set.
With a positive odd m.
m = 15; listOfIntegers =
RandomSample[Join[-Range[52, 1, -1], 0, Range[52]], 35]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-30, 19, 42, 38, -25, 6, 48, 5, -8, -27, -11, -47, -37, -12, -3,
-34, 50, 11, 10, 18, 7, -15, 51, -22, -26, -2, 33, -35, 34, 39, 44,
-51, -33, -16, -23
0.000468378, -35, 50, -33, 48, -27, 42, -23, 38, -3,
18, 5, 10
With a negative odd m.
m = -7; listOfIntegers =
RandomSample[Join[-Range[22, 1, -1], 0, Range[22]], 21]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-1, -16, -11, 10, 17, 1, 0, -5, -22, 8, -7, 15, 21, 11, 18, 14, -4,
7, -13, 4, -9
0.000310697, -22, 15, -11, 4, -7, 0
With a positive even m.
m = 36; listOfIntegers =
RandomSample[Join[-Range[30, 1, -1], 0, Range[30]], 20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
25, -9, -8, 8, 5, -10, -24, 13, 9, -16, -23, -14, -22, -29, 26, 12,
19, 16, -30, 18
0.000289237,
With a negative even m.
m = -34; listOfIntegers =
RandomSample[Join[-Range[100, 1, -1], 0, Range[100]], 50]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
7, 92, 91, 58, -58, 63, -95, 82, 26, 60, 16, 65, 15, 34, 29, 67, -2,
88, 21, -72, -93, 12, 43, 18, -83, -80, -30, -6, 54, -13, -63, 39,
-55, 9, -78, 5, -16, 52, -24, -82, -18, 2, -90, 37, -60, 80, 57, -22,
-26, 72
0.000726359, -63, 29, -60, 26, -55, 21, -18, -16
With m == 0.
m = 0; listOfIntegers =
RandomSample[Join[-Range[222, 1, -1], 0, Range[222]], 111]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-215, -8, 186, 153, 17, 83, 149, -45, -18, 14, -161, 6, 84, -41,
-59, -130, 34, -24, -142, -95, -70, -60, -152, 90, -43, 12, -196,
-98, -193, -78, -192, 7, -30, 218, -209, -28, -125, 142, 11, 161,
-143, -135, -212, 134, 1, -177, -100, 2, 63, -180, -50, 79, -129,
-91, 126, 57, -140, -200, 38, -182, -107, -25, -46, -179, -113, 88,
148, 28, 184, -158, 190, -9, -36, -5, 169, 221, -204, -210, 44, 45,
-71, 40, 135, 119, -42, 166, 65, 59, -15, -118, 117, -47, -52, 102,
74, -19, 152, 81, 0, 170, -214, 114, -38, 210, -1, -7, -89, -173,
123, 78, -127
0.00179934, -210, 210, -161, 161, -152, 152, -142,
142, -135, 135, -78, 78, -59, 59, -45, 45, -38,
38, -28, 28, -7, 7, -1, 1
With a large m with a large listOfIntegers.
m = 5311; listOfIntegers =
RandomSample[Join[-Range[9999, 1, -1], 0, Range[9999]], 8888];
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
0.209207, -4680, 9991, -4676, 9987, -4664, 9975, -4650,
9961, -4646, 9957, -4645, 9956, -4636, 9947, -4634,
9945, -4633, 9944, -4630, 9941, -4600, 9911, -4599,
9910, -4594, 9905, -4587, 9898, -4574, 9885, -4573,
9884, -4572, 9883, -4566, 9877, -4562, 9873, -4556,
9867, -4549, 9860, -4538, 9849, -4529, 9840, -4517,
9828, -4514, 9825, -4511, 9822, -4504, 9815, -4502,
9813, -4499, 9810, -4497, 9808, -4490, 9801, -4486,
9797, -4485, 9796, -4483, 9794, -4481, 9792, -4478,
9789, -4475, 9786, -4464, 9775, -4463, 9774, -4458,
9769, -4452, 9763, -4443, 9754, -4431, 9742, -4428,
9739, -4427, 9738, -4420, 9731, -4417, 9728, -4407,
9718, -4405, 9716, -4397, 9708, -4394, 9705, -4393,
9704, -4380, 9691, -4377, 9688, -4369, 9680, -4359,
9670, -4356, 9667, -4354, 9665, -4350, 9661, -4349,
9660, -4346, 9657, -4337, 9648, -4332, 9643, -4331,
9642, -4325, 9636, -4323, 9634, -4314, 9625, -4305,
9616, -4293, 9604, -4283, 9594, -4266, 9577, -4246,
9557, -4241, 9552, -4235, 9546, -4231, 9542, -4227,
9538, -4224, 9535, -4222, 9533, -4220, 9531, -4211,
9522, -4203, 9514, -4202, 9513, -4198, 9509, -4196,
9507, -4193, 9504, -4190, 9501, -4181, 9492, -4176,
9487, -4148, 9459, -4138, 9449, -4137, 9448, -4136,
9447, -4127, 9438, -4125, 9436, -4107, 9418, -4086,
9397, -4081, 9392, -4079, 9390, -4078, 9389, -4065,
9376, -4056, 9367, -4041, 9352, -4040, 9351, -4038,
9349, -4035, 9346, -4030, 9341, -4026, 9337, -4020,
9331, -4015, 9326, -4014, 9325, -4010, 9321, -3991,
9302, -3988, 9299, -3984, 9295, -3980, 9291, -3978,
9289, -3977, 9288, -3976, 9287, -3971, 9282, -3970,
9281, -3950, 9261, -3946, 9257, -3938, 9249, -3932,
9243, -3922, 9233, -3920, 9231, -3915, 9226, -3910,
9221, -3909, 9220, -3908, 9219, -3901, 9212, -3900,
9211, -3898, 9209, -3887, 9198, -3885, 9196, -3877,
9188, -3875, 9186, -3869, 9180, -3864, 9175, -3859,
9170, -3854, 9165, -3853, 9164, -3848, 9159, -3839,
9150, -3835, 9146, -3826, 9137, -3821, 9132, -3812,
9123, -3810, 9121, -3807, 9118, -3806, 9117, -3799,
9110, -3797, 9108, -3789, 9100, -3779, 9090, -3777,
9088, -3774, 9085, -3773, 9084, -3769, 9080, -3767,
9078, -3761, 9072, -3751, 9062, -3750, 9061, -3749,
9060, -3748, 9059, -3742, 9053, -3740, 9051, -3731,
9042, -3726, 9037, -3717, 9028, -3715, 9026, -3714,
9025, -3708, 9019, -3704, 9015, -3702, 9013, -3687,
8998, -3677, 8988, -3661, 8972, -3654, 8965, -3653,
8964, -3649, 8960, -3641, 8952, -3635, 8946, -3622,
8933, -3615, 8926, -3610, 8921, -3607, 8918, -3601,
8912, -3597, 8908, -3592, 8903, -3586, 8897, ... , 2594, 2717, 2598, 2713, 2599, 2712, 2603,
2708, 2607, 2704, 2617, 2694, 2619, 2692, 2633,
2678, 2634, 2677, 2643, 2668, 2644, 2667, 2648,
2663, 2650, 2661
algorithm code-review
edited 4 hours ago
Henrik Schumacher
57.7k579158
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
2
$begingroup$
I wrote a module in Mathematica which finds all possible pairs of integers from a specified list of integers (which can be negative, zero, or positive) which sum to a specified integer m.
The only limiting assumption this algorithm has is that the user only wishes to get the set of all unique sums which sum to m.
Is there a faster algorithm to do this? I've read that making a Hash table is of complexity O(n). Is my code of time O(n)? If it of time O(n), is it a Hash table, or is it something else? If it is not of time O(n), how efficient is it?
FindTwoIntegersWhoseSumIsM[listOfIntegers_,m_]:=Module[
i,distanceFrom1ToMin,negativeFactor,distance,start,finish,(*Integers*)
sortedList,numberLine,temp,finalList,(*Lists*)
execute(*Boolean*)
,
(*There are possible inputted values of m with a give integer set input which
make the execution of this algorithm unnecessary.*)
execute=True;
sortedList=Sort[DeleteDuplicates[listOfIntegers]];
(*Create a continuous list of integers whose smallest and largest entries is equal
to the smallest and largest entries of the inputted list of integers, respectively.*)
(*Let this list be named numberline.*)
(*:::::Construction of numberline BEGINS::::*)
(*If the listOfIntegers only contains negative integers and possibly zero,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]<=0),
(*If m is positive, there is no reason to proceed.*)
If[m>0,execute=False,
(*If m [Equal] 0 then if two or more zeros are in listOfIntegers, they should be outputted to the user.
Therefore, we write m>0 instead of m[GreaterEqual]0 in the conditional above.*)
(*Otherwise, treat it as if all integers were positive with a few considerations.*)
negativeFactor=-1;
sortedList=Reverse[-sortedList];
If[sortedList[[1]]!=0,
numberLine=Range[sortedList[[Length[sortedList]]]]
,
numberLine=Join[0,Range[sortedList[[Length[sortedList]]]]]
]
]
,
negativeFactor=1;
(*Else If the integer set contains negative and positive integers,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]>0),
numberLine=
Join[
-Range[Abs[sortedList[[1]]],0,-1](*negative integer subset*)
,
Range[sortedList[[Length[sortedList]]]](*positive integer subset*)
]
,(*Else if the integer set contains only whole numbers,*)
If[(sortedList[[1]]==0)&&(sortedList[[Length[sortedList]]]>0),
(*If the list of integers are all positive and m is negative,
there is no reason to proceed.*)
If[m<0,execute=False,(*Otherwise,*)
numberLine=
Join[
0(*zero*)
,
Range[sortedList[[Length[sortedList]]]](*positive integers*)
]
]
,(*Else if the integer set contains only the natural numbers.*)
(*If the list of integers are all positive and m is negative or zero,
there is no reason to proceed.*)
If[m<=0,execute=False,numberLine=Range[Max[sortedList](*positive integers*)]]
]
]
];
(*:::::Construction of numberline ENDS::::*)
(*Print[numberLine];*)
If[execute==False,finalList=$Failed,
(*Mark all numbers which are in numberline but are not in listOfIntegers with a period.
Sort[] will still sort this list of mixed precision of numbers in ascending order.*)
temp=Sort[Join[Complement[numberLine,sortedList]//N,sortedList]];
(*The main idea of the algorithm is to find the point on numberline to begin selecting two number
combinations which sum to m. m is obviously going to be used when that time comes.
Once that point is selected, integers symmetrically equally distant apart from each other
on both sides of this point (number) in numberline are candidates which sum to m.
To avoid going "out of bounds" of numberline (from either attempting to select a value smaller
than the minimum value of numberline or attempting to select a larger value than the maximum
value of numberline, the following is the maximum distance we can use to obtain ALL possible
two integer combinations which sum to m but of which also prevents us from going "out of bounds".)
*)
(*If the numberline we are about to create had a consistent minimum value of 1
then it would not be offset as it is in general.
The following takes this "offset" into account.*)
distanceFrom1ToMin=Abs[1-Min[sortedList]];
distance=
Min[
distanceFrom1ToMin+Floor[negativeFactor*m/2]
,
Length[temp]-(distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1)
];
start=distanceFrom1ToMin+Floor[negativeFactor*m/2]+1;
finish=distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1;
(*With the bound distance established, we are ready to begin selecting numbers from numberline.*)
finalList=;
i=1;
While[i<=distance,
finalList=Append[finalList,temp[[start-i]],temp[[finish+i]]];
i++
];
(*It turns out that for even m the first selected integer combination considered is m/2,m/2.*)
If[(Mod[m,2]==0)&&(MemberQ[finalList,negativeFactor*m/2,negativeFactor*m/2]==True),
(*Should there not be two of m/2 in listOfIntegers, we omit this selected combination.*)
If[Length[Flatten[Position[listOfIntegers,negativeFactor*m/2]]]<2,
finalList=Delete[finalList,Position[finalList,negativeFactor*m/2,negativeFactor*m/2][[1]][[1]]]
]
];
(*We selected all possible number combinations in numberline. However, unless listOfIntegers
is all consecutive integers, we need to omit any selected number combination in which either
of the numbers has a "." to the right of it.*)
finalList=negativeFactor*Sort[Select[finalList,Precision[#]==[Infinity]&]]
];
finalList
]
I did the following tests with the code and got these results. (The first number in the time in second it took to do the computation. But you can of course copy the code and do tests yourself.) I omitted most of the results from the last test because it made my post too large, but you will see that it did the computation in 0.209207 seconds.
As the comments in my algorithm (and the algorithm itself suggests), I broke up the number line into negative integers, zero, and the positive integers. I therefore wrote my tests to address all possible situations.
For the positive (non-zero) integer set.
With positive m such that m is larger than what any two number combination in listOfIntegers could possibly sum to.
m = 100; listOfIntegers = RandomSample[Range[20], 6]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
19, 11, 1, 4, 13, 17
0.0371008,
With positive odd m.
m = 215; listOfIntegers = RandomSample[Range[266], 190]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
119, 175, 7, 123, 42, 173, 15, 56, 233, 41, 9, 156, 130, 196, 183,
65, 102, 109, 177, 161, 230, 105, 91, 103, 146, 47, 234, 133, 88, 68,
169, 197, 46, 198, 108, 263, 205, 129, 4, 157, 245, 210, 203, 78,
172, 128, 138, 61, 262, 159, 148, 45, 225, 239, 72, 74, 151, 34, 36,
5, 106, 77, 223, 116, 8, 2, 11, 54, 124, 87, 221, 213, 171, 93, 53,
19, 40, 30, 95, 215, 39, 140, 49, 158, 94, 38, 28, 247, 84, 75, 257,
33, 163, 132, 69, 211, 193, 222, 114, 240, 32, 149, 167, 135, 107,
115, 101, 100, 166, 144, 251, 253, 224, 154, 48, 44, 26, 181, 259,
81, 6, 70, 122, 255, 189, 235, 112, 110, 174, 85, 147, 117, 18, 209,
66, 121, 155, 206, 207, 212, 98, 113, 254, 214, 178, 111, 227, 165,
204, 231, 194, 20, 176, 150, 162, 241, 243, 199, 90, 55, 127, 191,
12, 185, 242, 125, 265, 25, 1, 250, 201, 168, 76, 134, 266, 82, 10,
92, 143, 217, 126, 218, 182, 220, 153, 164, 216, 238, 67, 14
0.136695, 1, 214, 2, 213, 4, 211, 5, 210, 6, 209, 8,
207, 9, 206, 10, 205, 11, 204, 12, 203, 14, 201, 18,
197, 19, 196, 26, 189, 30, 185, 32, 183, 33, 182, 34,
181, 38, 177, 39, 176, 40, 175, 41, 174, 42, 173, 44,
171, 46, 169, 47, 168, 48, 167, 49, 166, 53, 162, 54,
161, 56, 159, 61, 154, 65, 150, 66, 149, 67, 148, 68,
147, 69, 146, 72, 143, 75, 140, 77, 138, 81, 134, 82,
133, 85, 130, 87, 128, 88, 127, 90, 125, 91, 124, 92,
123, 93, 122, 94, 121, 98, 117, 100, 115, 101,
114, 102, 113, 103, 112, 105, 110, 106, 109, 107, 108
With positive even m.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.00998522, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With positive even m such that listOfIntegers contains two of m/2.
m = 22; listOfIntegers = Append[Range[20], 11]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 11
0.00037181, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12, 11, 11
With positive even m such that listOfIntegers contains one m/2.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.000267311, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With any negative m.
m = -6; listOfIntegers = Range[26]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26
0.000108231, $Failed
For the positive integer set (including 0).
With an even m.
m = 88; listOfIntegers = RandomSample[Join[0, Range[122]], 39]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
121, 69, 120, 56, 36, 55, 17, 114, 7, 59, 32, 4, 20, 79, 92, 62, 50,
89, 13, 70, 113, 75, 76, 80, 108, 53, 83, 95, 0, 85, 86, 77, 10, 54,
48, 66, 104, 100, 35
0.000505232, 13, 75, 32, 56, 35, 53
With an odd m.
m = 57; listOfIntegers = RandomSample[Join[0, Range[82]], 52]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
62, 18, 26, 0, 67, 34, 55, 52, 35, 78, 10, 68, 46, 44, 38, 23, 77,
76, 58, 51, 75, 63, 53, 42, 54, 27, 56, 71, 12, 17, 2, 37, 31, 72,
49, 50, 32, 16, 47, 19, 4, 20, 81, 25, 61, 14, 80, 82, 59, 33, 70, 39
0.000372743, 2, 55, 4, 53, 10, 47, 18, 39, 19, 38, 20,
37, 23, 34, 25, 32, 26, 31
For the negative integer set (including 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-2, -16, -15, -9, -5, -12, -8, -22, -7, -21, -13, -18, -4, -11, -10,
-19, -6, -17, -20
0.000105898, $Failed
With a negative odd m.
m = -17; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-5, -1, -10, -13, -15, -19, -2, 0, -7, -18, -3, -21, -8, -11, -12,
-22, -17, -16, -20
0.000640987, 0, -17, -1, -16, -2, -15, -5, -12, -7, -10
With a negative even m.
m = -26; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -16, -11, -14, -17, -13, -1, -9, -15, -20, -18, -4, -21, 0, -8,
-6, -10, -7, -3
0.000329357, -6, -20, -7, -19, -8, -18, -9, -17, -10,
-16, -11, -15
For the negative integer set (excluding 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-20, -7, -16, -21, -11, -13, -5, -2, -6, -19, -1, -12, -18, -14,
-15, -9, -4, -17, -22
0.000102633, $Failed
With a negative odd m.
m = -27; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-18, -17, -22, -13, -1, -11, -19, -8, -16, -6, -21, -12, -20, -3,
-4, -9, -7, -14, -15
0.000242586, -6, -21, -7, -20, -8, -19, -9, -18, -11,
-16, -12, -15, -13, -14
With a negative even m.
m = -26; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -10, -20, -9, -21, -14, -5, -1, -17, -4, -18, -22, -8, -6, -13,
-3, -2, -12, -15
0.000286438, -4, -22, -5, -21, -6, -20, -8, -18, -9, -17,
-12, -14
For the complete integer set.
With a positive odd m.
m = 15; listOfIntegers =
RandomSample[Join[-Range[52, 1, -1], 0, Range[52]], 35]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-30, 19, 42, 38, -25, 6, 48, 5, -8, -27, -11, -47, -37, -12, -3,
-34, 50, 11, 10, 18, 7, -15, 51, -22, -26, -2, 33, -35, 34, 39, 44,
-51, -33, -16, -23
0.000468378, -35, 50, -33, 48, -27, 42, -23, 38, -3,
18, 5, 10
With a negative odd m.
m = -7; listOfIntegers =
RandomSample[Join[-Range[22, 1, -1], 0, Range[22]], 21]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-1, -16, -11, 10, 17, 1, 0, -5, -22, 8, -7, 15, 21, 11, 18, 14, -4,
7, -13, 4, -9
0.000310697, -22, 15, -11, 4, -7, 0
With a positive even m.
m = 36; listOfIntegers =
RandomSample[Join[-Range[30, 1, -1], 0, Range[30]], 20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
25, -9, -8, 8, 5, -10, -24, 13, 9, -16, -23, -14, -22, -29, 26, 12,
19, 16, -30, 18
0.000289237,
With a negative even m.
m = -34; listOfIntegers =
RandomSample[Join[-Range[100, 1, -1], 0, Range[100]], 50]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
7, 92, 91, 58, -58, 63, -95, 82, 26, 60, 16, 65, 15, 34, 29, 67, -2,
88, 21, -72, -93, 12, 43, 18, -83, -80, -30, -6, 54, -13, -63, 39,
-55, 9, -78, 5, -16, 52, -24, -82, -18, 2, -90, 37, -60, 80, 57, -22,
-26, 72
0.000726359, -63, 29, -60, 26, -55, 21, -18, -16
With m == 0.
m = 0; listOfIntegers =
RandomSample[Join[-Range[222, 1, -1], 0, Range[222]], 111]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-215, -8, 186, 153, 17, 83, 149, -45, -18, 14, -161, 6, 84, -41,
-59, -130, 34, -24, -142, -95, -70, -60, -152, 90, -43, 12, -196,
-98, -193, -78, -192, 7, -30, 218, -209, -28, -125, 142, 11, 161,
-143, -135, -212, 134, 1, -177, -100, 2, 63, -180, -50, 79, -129,
-91, 126, 57, -140, -200, 38, -182, -107, -25, -46, -179, -113, 88,
148, 28, 184, -158, 190, -9, -36, -5, 169, 221, -204, -210, 44, 45,
-71, 40, 135, 119, -42, 166, 65, 59, -15, -118, 117, -47, -52, 102,
74, -19, 152, 81, 0, 170, -214, 114, -38, 210, -1, -7, -89, -173,
123, 78, -127
0.00179934, -210, 210, -161, 161, -152, 152, -142,
142, -135, 135, -78, 78, -59, 59, -45, 45, -38,
38, -28, 28, -7, 7, -1, 1
With a large m with a large listOfIntegers.
m = 5311; listOfIntegers =
RandomSample[Join[-Range[9999, 1, -1], 0, Range[9999]], 8888];
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
0.209207, -4680, 9991, -4676, 9987, -4664, 9975, -4650,
9961, -4646, 9957, -4645, 9956, -4636, 9947, -4634,
9945, -4633, 9944, -4630, 9941, -4600, 9911, -4599,
9910, -4594, 9905, -4587, 9898, -4574, 9885, -4573,
9884, -4572, 9883, -4566, 9877, -4562, 9873, -4556,
9867, -4549, 9860, -4538, 9849, -4529, 9840, -4517,
9828, -4514, 9825, -4511, 9822, -4504, 9815, -4502,
9813, -4499, 9810, -4497, 9808, -4490, 9801, -4486,
9797, -4485, 9796, -4483, 9794, -4481, 9792, -4478,
9789, -4475, 9786, -4464, 9775, -4463, 9774, -4458,
9769, -4452, 9763, -4443, 9754, -4431, 9742, -4428,
9739, -4427, 9738, -4420, 9731, -4417, 9728, -4407,
9718, -4405, 9716, -4397, 9708, -4394, 9705, -4393,
9704, -4380, 9691, -4377, 9688, -4369, 9680, -4359,
9670, -4356, 9667, -4354, 9665, -4350, 9661, -4349,
9660, -4346, 9657, -4337, 9648, -4332, 9643, -4331,
9642, -4325, 9636, -4323, 9634, -4314, 9625, -4305,
9616, -4293, 9604, -4283, 9594, -4266, 9577, -4246,
9557, -4241, 9552, -4235, 9546, -4231, 9542, -4227,
9538, -4224, 9535, -4222, 9533, -4220, 9531, -4211,
9522, -4203, 9514, -4202, 9513, -4198, 9509, -4196,
9507, -4193, 9504, -4190, 9501, -4181, 9492, -4176,
9487, -4148, 9459, -4138, 9449, -4137, 9448, -4136,
9447, -4127, 9438, -4125, 9436, -4107, 9418, -4086,
9397, -4081, 9392, -4079, 9390, -4078, 9389, -4065,
9376, -4056, 9367, -4041, 9352, -4040, 9351, -4038,
9349, -4035, 9346, -4030, 9341, -4026, 9337, -4020,
9331, -4015, 9326, -4014, 9325, -4010, 9321, -3991,
9302, -3988, 9299, -3984, 9295, -3980, 9291, -3978,
9289, -3977, 9288, -3976, 9287, -3971, 9282, -3970,
9281, -3950, 9261, -3946, 9257, -3938, 9249, -3932,
9243, -3922, 9233, -3920, 9231, -3915, 9226, -3910,
9221, -3909, 9220, -3908, 9219, -3901, 9212, -3900,
9211, -3898, 9209, -3887, 9198, -3885, 9196, -3877,
9188, -3875, 9186, -3869, 9180, -3864, 9175, -3859,
9170, -3854, 9165, -3853, 9164, -3848, 9159, -3839,
9150, -3835, 9146, -3826, 9137, -3821, 9132, -3812,
9123, -3810, 9121, -3807, 9118, -3806, 9117, -3799,
9110, -3797, 9108, -3789, 9100, -3779, 9090, -3777,
9088, -3774, 9085, -3773, 9084, -3769, 9080, -3767,
9078, -3761, 9072, -3751, 9062, -3750, 9061, -3749,
9060, -3748, 9059, -3742, 9053, -3740, 9051, -3731,
9042, -3726, 9037, -3717, 9028, -3715, 9026, -3714,
9025, -3708, 9019, -3704, 9015, -3702, 9013, -3687,
8998, -3677, 8988, -3661, 8972, -3654, 8965, -3653,
8964, -3649, 8960, -3641, 8952, -3635, 8946, -3622,
8933, -3615, 8926, -3610, 8921, -3607, 8918, -3601,
8912, -3597, 8908, -3592, 8903, -3586, 8897, ... , 2594, 2717, 2598, 2713, 2599, 2712, 2603,
2708, 2607, 2704, 2617, 2694, 2619, 2692, 2633,
2678, 2634, 2677, 2643, 2668, 2644, 2667, 2648,
2663, 2650, 2661
algorithm code-review
edited 4 hours ago
Henrik Schumacher
57.7k579158
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
The presence of anAppendindicates that the complexity of the algorithm is larger than you expect...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
You have aSortcall. UseSortByinstead, it is much faster thanSort. But you probably don't need to sort it anyway.
$endgroup$
– MikeY
3 hours ago
$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
32 mins ago
add a comment |
2
2
2
$begingroup$
I wrote a module in Mathematica which finds all possible pairs of integers from a specified list of integers (which can be negative, zero, or positive) which sum to a specified integer m.
The only limiting assumption this algorithm has is that the user only wishes to get the set of all unique sums which sum to m.
Is there a faster algorithm to do this? I've read that making a Hash table is of complexity O(n). Is my code of time O(n)? If it of time O(n), is it a Hash table, or is it something else? If it is not of time O(n), how efficient is it?
FindTwoIntegersWhoseSumIsM[listOfIntegers_,m_]:=Module[
i,distanceFrom1ToMin,negativeFactor,distance,start,finish,(*Integers*)
sortedList,numberLine,temp,finalList,(*Lists*)
execute(*Boolean*)
,
(*There are possible inputted values of m with a give integer set input which
make the execution of this algorithm unnecessary.*)
execute=True;
sortedList=Sort[DeleteDuplicates[listOfIntegers]];
(*Create a continuous list of integers whose smallest and largest entries is equal
to the smallest and largest entries of the inputted list of integers, respectively.*)
(*Let this list be named numberline.*)
(*:::::Construction of numberline BEGINS::::*)
(*If the listOfIntegers only contains negative integers and possibly zero,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]<=0),
(*If m is positive, there is no reason to proceed.*)
If[m>0,execute=False,
(*If m [Equal] 0 then if two or more zeros are in listOfIntegers, they should be outputted to the user.
Therefore, we write m>0 instead of m[GreaterEqual]0 in the conditional above.*)
(*Otherwise, treat it as if all integers were positive with a few considerations.*)
negativeFactor=-1;
sortedList=Reverse[-sortedList];
If[sortedList[[1]]!=0,
numberLine=Range[sortedList[[Length[sortedList]]]]
,
numberLine=Join[0,Range[sortedList[[Length[sortedList]]]]]
]
]
,
negativeFactor=1;
(*Else If the integer set contains negative and positive integers,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]>0),
numberLine=
Join[
-Range[Abs[sortedList[[1]]],0,-1](*negative integer subset*)
,
Range[sortedList[[Length[sortedList]]]](*positive integer subset*)
]
,(*Else if the integer set contains only whole numbers,*)
If[(sortedList[[1]]==0)&&(sortedList[[Length[sortedList]]]>0),
(*If the list of integers are all positive and m is negative,
there is no reason to proceed.*)
If[m<0,execute=False,(*Otherwise,*)
numberLine=
Join[
0(*zero*)
,
Range[sortedList[[Length[sortedList]]]](*positive integers*)
]
]
,(*Else if the integer set contains only the natural numbers.*)
(*If the list of integers are all positive and m is negative or zero,
there is no reason to proceed.*)
If[m<=0,execute=False,numberLine=Range[Max[sortedList](*positive integers*)]]
]
]
];
(*:::::Construction of numberline ENDS::::*)
(*Print[numberLine];*)
If[execute==False,finalList=$Failed,
(*Mark all numbers which are in numberline but are not in listOfIntegers with a period.
Sort[] will still sort this list of mixed precision of numbers in ascending order.*)
temp=Sort[Join[Complement[numberLine,sortedList]//N,sortedList]];
(*The main idea of the algorithm is to find the point on numberline to begin selecting two number
combinations which sum to m. m is obviously going to be used when that time comes.
Once that point is selected, integers symmetrically equally distant apart from each other
on both sides of this point (number) in numberline are candidates which sum to m.
To avoid going "out of bounds" of numberline (from either attempting to select a value smaller
than the minimum value of numberline or attempting to select a larger value than the maximum
value of numberline, the following is the maximum distance we can use to obtain ALL possible
two integer combinations which sum to m but of which also prevents us from going "out of bounds".)
*)
(*If the numberline we are about to create had a consistent minimum value of 1
then it would not be offset as it is in general.
The following takes this "offset" into account.*)
distanceFrom1ToMin=Abs[1-Min[sortedList]];
distance=
Min[
distanceFrom1ToMin+Floor[negativeFactor*m/2]
,
Length[temp]-(distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1)
];
start=distanceFrom1ToMin+Floor[negativeFactor*m/2]+1;
finish=distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1;
(*With the bound distance established, we are ready to begin selecting numbers from numberline.*)
finalList=;
i=1;
While[i<=distance,
finalList=Append[finalList,temp[[start-i]],temp[[finish+i]]];
i++
];
(*It turns out that for even m the first selected integer combination considered is m/2,m/2.*)
If[(Mod[m,2]==0)&&(MemberQ[finalList,negativeFactor*m/2,negativeFactor*m/2]==True),
(*Should there not be two of m/2 in listOfIntegers, we omit this selected combination.*)
If[Length[Flatten[Position[listOfIntegers,negativeFactor*m/2]]]<2,
finalList=Delete[finalList,Position[finalList,negativeFactor*m/2,negativeFactor*m/2][[1]][[1]]]
]
];
(*We selected all possible number combinations in numberline. However, unless listOfIntegers
is all consecutive integers, we need to omit any selected number combination in which either
of the numbers has a "." to the right of it.*)
finalList=negativeFactor*Sort[Select[finalList,Precision[#]==[Infinity]&]]
];
finalList
]
I did the following tests with the code and got these results. (The first number in the time in second it took to do the computation. But you can of course copy the code and do tests yourself.) I omitted most of the results from the last test because it made my post too large, but you will see that it did the computation in 0.209207 seconds.
As the comments in my algorithm (and the algorithm itself suggests), I broke up the number line into negative integers, zero, and the positive integers. I therefore wrote my tests to address all possible situations.
For the positive (non-zero) integer set.
With positive m such that m is larger than what any two number combination in listOfIntegers could possibly sum to.
m = 100; listOfIntegers = RandomSample[Range[20], 6]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
19, 11, 1, 4, 13, 17
0.0371008,
With positive odd m.
m = 215; listOfIntegers = RandomSample[Range[266], 190]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
119, 175, 7, 123, 42, 173, 15, 56, 233, 41, 9, 156, 130, 196, 183,
65, 102, 109, 177, 161, 230, 105, 91, 103, 146, 47, 234, 133, 88, 68,
169, 197, 46, 198, 108, 263, 205, 129, 4, 157, 245, 210, 203, 78,
172, 128, 138, 61, 262, 159, 148, 45, 225, 239, 72, 74, 151, 34, 36,
5, 106, 77, 223, 116, 8, 2, 11, 54, 124, 87, 221, 213, 171, 93, 53,
19, 40, 30, 95, 215, 39, 140, 49, 158, 94, 38, 28, 247, 84, 75, 257,
33, 163, 132, 69, 211, 193, 222, 114, 240, 32, 149, 167, 135, 107,
115, 101, 100, 166, 144, 251, 253, 224, 154, 48, 44, 26, 181, 259,
81, 6, 70, 122, 255, 189, 235, 112, 110, 174, 85, 147, 117, 18, 209,
66, 121, 155, 206, 207, 212, 98, 113, 254, 214, 178, 111, 227, 165,
204, 231, 194, 20, 176, 150, 162, 241, 243, 199, 90, 55, 127, 191,
12, 185, 242, 125, 265, 25, 1, 250, 201, 168, 76, 134, 266, 82, 10,
92, 143, 217, 126, 218, 182, 220, 153, 164, 216, 238, 67, 14
0.136695, 1, 214, 2, 213, 4, 211, 5, 210, 6, 209, 8,
207, 9, 206, 10, 205, 11, 204, 12, 203, 14, 201, 18,
197, 19, 196, 26, 189, 30, 185, 32, 183, 33, 182, 34,
181, 38, 177, 39, 176, 40, 175, 41, 174, 42, 173, 44,
171, 46, 169, 47, 168, 48, 167, 49, 166, 53, 162, 54,
161, 56, 159, 61, 154, 65, 150, 66, 149, 67, 148, 68,
147, 69, 146, 72, 143, 75, 140, 77, 138, 81, 134, 82,
133, 85, 130, 87, 128, 88, 127, 90, 125, 91, 124, 92,
123, 93, 122, 94, 121, 98, 117, 100, 115, 101,
114, 102, 113, 103, 112, 105, 110, 106, 109, 107, 108
With positive even m.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.00998522, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With positive even m such that listOfIntegers contains two of m/2.
m = 22; listOfIntegers = Append[Range[20], 11]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 11
0.00037181, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12, 11, 11
With positive even m such that listOfIntegers contains one m/2.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.000267311, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With any negative m.
m = -6; listOfIntegers = Range[26]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26
0.000108231, $Failed
For the positive integer set (including 0).
With an even m.
m = 88; listOfIntegers = RandomSample[Join[0, Range[122]], 39]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
121, 69, 120, 56, 36, 55, 17, 114, 7, 59, 32, 4, 20, 79, 92, 62, 50,
89, 13, 70, 113, 75, 76, 80, 108, 53, 83, 95, 0, 85, 86, 77, 10, 54,
48, 66, 104, 100, 35
0.000505232, 13, 75, 32, 56, 35, 53
With an odd m.
m = 57; listOfIntegers = RandomSample[Join[0, Range[82]], 52]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
62, 18, 26, 0, 67, 34, 55, 52, 35, 78, 10, 68, 46, 44, 38, 23, 77,
76, 58, 51, 75, 63, 53, 42, 54, 27, 56, 71, 12, 17, 2, 37, 31, 72,
49, 50, 32, 16, 47, 19, 4, 20, 81, 25, 61, 14, 80, 82, 59, 33, 70, 39
0.000372743, 2, 55, 4, 53, 10, 47, 18, 39, 19, 38, 20,
37, 23, 34, 25, 32, 26, 31
For the negative integer set (including 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-2, -16, -15, -9, -5, -12, -8, -22, -7, -21, -13, -18, -4, -11, -10,
-19, -6, -17, -20
0.000105898, $Failed
With a negative odd m.
m = -17; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-5, -1, -10, -13, -15, -19, -2, 0, -7, -18, -3, -21, -8, -11, -12,
-22, -17, -16, -20
0.000640987, 0, -17, -1, -16, -2, -15, -5, -12, -7, -10
With a negative even m.
m = -26; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -16, -11, -14, -17, -13, -1, -9, -15, -20, -18, -4, -21, 0, -8,
-6, -10, -7, -3
0.000329357, -6, -20, -7, -19, -8, -18, -9, -17, -10,
-16, -11, -15
For the negative integer set (excluding 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-20, -7, -16, -21, -11, -13, -5, -2, -6, -19, -1, -12, -18, -14,
-15, -9, -4, -17, -22
0.000102633, $Failed
With a negative odd m.
m = -27; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-18, -17, -22, -13, -1, -11, -19, -8, -16, -6, -21, -12, -20, -3,
-4, -9, -7, -14, -15
0.000242586, -6, -21, -7, -20, -8, -19, -9, -18, -11,
-16, -12, -15, -13, -14
With a negative even m.
m = -26; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -10, -20, -9, -21, -14, -5, -1, -17, -4, -18, -22, -8, -6, -13,
-3, -2, -12, -15
0.000286438, -4, -22, -5, -21, -6, -20, -8, -18, -9, -17,
-12, -14
For the complete integer set.
With a positive odd m.
m = 15; listOfIntegers =
RandomSample[Join[-Range[52, 1, -1], 0, Range[52]], 35]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-30, 19, 42, 38, -25, 6, 48, 5, -8, -27, -11, -47, -37, -12, -3,
-34, 50, 11, 10, 18, 7, -15, 51, -22, -26, -2, 33, -35, 34, 39, 44,
-51, -33, -16, -23
0.000468378, -35, 50, -33, 48, -27, 42, -23, 38, -3,
18, 5, 10
With a negative odd m.
m = -7; listOfIntegers =
RandomSample[Join[-Range[22, 1, -1], 0, Range[22]], 21]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-1, -16, -11, 10, 17, 1, 0, -5, -22, 8, -7, 15, 21, 11, 18, 14, -4,
7, -13, 4, -9
0.000310697, -22, 15, -11, 4, -7, 0
With a positive even m.
m = 36; listOfIntegers =
RandomSample[Join[-Range[30, 1, -1], 0, Range[30]], 20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
25, -9, -8, 8, 5, -10, -24, 13, 9, -16, -23, -14, -22, -29, 26, 12,
19, 16, -30, 18
0.000289237,
With a negative even m.
m = -34; listOfIntegers =
RandomSample[Join[-Range[100, 1, -1], 0, Range[100]], 50]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
7, 92, 91, 58, -58, 63, -95, 82, 26, 60, 16, 65, 15, 34, 29, 67, -2,
88, 21, -72, -93, 12, 43, 18, -83, -80, -30, -6, 54, -13, -63, 39,
-55, 9, -78, 5, -16, 52, -24, -82, -18, 2, -90, 37, -60, 80, 57, -22,
-26, 72
0.000726359, -63, 29, -60, 26, -55, 21, -18, -16
With m == 0.
m = 0; listOfIntegers =
RandomSample[Join[-Range[222, 1, -1], 0, Range[222]], 111]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-215, -8, 186, 153, 17, 83, 149, -45, -18, 14, -161, 6, 84, -41,
-59, -130, 34, -24, -142, -95, -70, -60, -152, 90, -43, 12, -196,
-98, -193, -78, -192, 7, -30, 218, -209, -28, -125, 142, 11, 161,
-143, -135, -212, 134, 1, -177, -100, 2, 63, -180, -50, 79, -129,
-91, 126, 57, -140, -200, 38, -182, -107, -25, -46, -179, -113, 88,
148, 28, 184, -158, 190, -9, -36, -5, 169, 221, -204, -210, 44, 45,
-71, 40, 135, 119, -42, 166, 65, 59, -15, -118, 117, -47, -52, 102,
74, -19, 152, 81, 0, 170, -214, 114, -38, 210, -1, -7, -89, -173,
123, 78, -127
0.00179934, -210, 210, -161, 161, -152, 152, -142,
142, -135, 135, -78, 78, -59, 59, -45, 45, -38,
38, -28, 28, -7, 7, -1, 1
With a large m with a large listOfIntegers.
m = 5311; listOfIntegers =
RandomSample[Join[-Range[9999, 1, -1], 0, Range[9999]], 8888];
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
0.209207, -4680, 9991, -4676, 9987, -4664, 9975, -4650,
9961, -4646, 9957, -4645, 9956, -4636, 9947, -4634,
9945, -4633, 9944, -4630, 9941, -4600, 9911, -4599,
9910, -4594, 9905, -4587, 9898, -4574, 9885, -4573,
9884, -4572, 9883, -4566, 9877, -4562, 9873, -4556,
9867, -4549, 9860, -4538, 9849, -4529, 9840, -4517,
9828, -4514, 9825, -4511, 9822, -4504, 9815, -4502,
9813, -4499, 9810, -4497, 9808, -4490, 9801, -4486,
9797, -4485, 9796, -4483, 9794, -4481, 9792, -4478,
9789, -4475, 9786, -4464, 9775, -4463, 9774, -4458,
9769, -4452, 9763, -4443, 9754, -4431, 9742, -4428,
9739, -4427, 9738, -4420, 9731, -4417, 9728, -4407,
9718, -4405, 9716, -4397, 9708, -4394, 9705, -4393,
9704, -4380, 9691, -4377, 9688, -4369, 9680, -4359,
9670, -4356, 9667, -4354, 9665, -4350, 9661, -4349,
9660, -4346, 9657, -4337, 9648, -4332, 9643, -4331,
9642, -4325, 9636, -4323, 9634, -4314, 9625, -4305,
9616, -4293, 9604, -4283, 9594, -4266, 9577, -4246,
9557, -4241, 9552, -4235, 9546, -4231, 9542, -4227,
9538, -4224, 9535, -4222, 9533, -4220, 9531, -4211,
9522, -4203, 9514, -4202, 9513, -4198, 9509, -4196,
9507, -4193, 9504, -4190, 9501, -4181, 9492, -4176,
9487, -4148, 9459, -4138, 9449, -4137, 9448, -4136,
9447, -4127, 9438, -4125, 9436, -4107, 9418, -4086,
9397, -4081, 9392, -4079, 9390, -4078, 9389, -4065,
9376, -4056, 9367, -4041, 9352, -4040, 9351, -4038,
9349, -4035, 9346, -4030, 9341, -4026, 9337, -4020,
9331, -4015, 9326, -4014, 9325, -4010, 9321, -3991,
9302, -3988, 9299, -3984, 9295, -3980, 9291, -3978,
9289, -3977, 9288, -3976, 9287, -3971, 9282, -3970,
9281, -3950, 9261, -3946, 9257, -3938, 9249, -3932,
9243, -3922, 9233, -3920, 9231, -3915, 9226, -3910,
9221, -3909, 9220, -3908, 9219, -3901, 9212, -3900,
9211, -3898, 9209, -3887, 9198, -3885, 9196, -3877,
9188, -3875, 9186, -3869, 9180, -3864, 9175, -3859,
9170, -3854, 9165, -3853, 9164, -3848, 9159, -3839,
9150, -3835, 9146, -3826, 9137, -3821, 9132, -3812,
9123, -3810, 9121, -3807, 9118, -3806, 9117, -3799,
9110, -3797, 9108, -3789, 9100, -3779, 9090, -3777,
9088, -3774, 9085, -3773, 9084, -3769, 9080, -3767,
9078, -3761, 9072, -3751, 9062, -3750, 9061, -3749,
9060, -3748, 9059, -3742, 9053, -3740, 9051, -3731,
9042, -3726, 9037, -3717, 9028, -3715, 9026, -3714,
9025, -3708, 9019, -3704, 9015, -3702, 9013, -3687,
8998, -3677, 8988, -3661, 8972, -3654, 8965, -3653,
8964, -3649, 8960, -3641, 8952, -3635, 8946, -3622,
8933, -3615, 8926, -3610, 8921, -3607, 8918, -3601,
8912, -3597, 8908, -3592, 8903, -3586, 8897, ... , 2594, 2717, 2598, 2713, 2599, 2712, 2603,
2708, 2607, 2704, 2617, 2694, 2619, 2692, 2633,
2678, 2634, 2677, 2643, 2668, 2644, 2667, 2648,
2663, 2650, 2661
algorithm code-review
edited 4 hours ago
Henrik Schumacher
57.7k579158
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I wrote a module in Mathematica which finds all possible pairs of integers from a specified list of integers (which can be negative, zero, or positive) which sum to a specified integer m.
The only limiting assumption this algorithm has is that the user only wishes to get the set of all unique sums which sum to m.
Is there a faster algorithm to do this? I've read that making a Hash table is of complexity O(n). Is my code of time O(n)? If it of time O(n), is it a Hash table, or is it something else? If it is not of time O(n), how efficient is it?
FindTwoIntegersWhoseSumIsM[listOfIntegers_,m_]:=Module[
i,distanceFrom1ToMin,negativeFactor,distance,start,finish,(*Integers*)
sortedList,numberLine,temp,finalList,(*Lists*)
execute(*Boolean*)
,
(*There are possible inputted values of m with a give integer set input which
make the execution of this algorithm unnecessary.*)
execute=True;
sortedList=Sort[DeleteDuplicates[listOfIntegers]];
(*Create a continuous list of integers whose smallest and largest entries is equal
to the smallest and largest entries of the inputted list of integers, respectively.*)
(*Let this list be named numberline.*)
(*:::::Construction of numberline BEGINS::::*)
(*If the listOfIntegers only contains negative integers and possibly zero,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]<=0),
(*If m is positive, there is no reason to proceed.*)
If[m>0,execute=False,
(*If m [Equal] 0 then if two or more zeros are in listOfIntegers, they should be outputted to the user.
Therefore, we write m>0 instead of m[GreaterEqual]0 in the conditional above.*)
(*Otherwise, treat it as if all integers were positive with a few considerations.*)
negativeFactor=-1;
sortedList=Reverse[-sortedList];
If[sortedList[[1]]!=0,
numberLine=Range[sortedList[[Length[sortedList]]]]
,
numberLine=Join[0,Range[sortedList[[Length[sortedList]]]]]
]
]
,
negativeFactor=1;
(*Else If the integer set contains negative and positive integers,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]>0),
numberLine=
Join[
-Range[Abs[sortedList[[1]]],0,-1](*negative integer subset*)
,
Range[sortedList[[Length[sortedList]]]](*positive integer subset*)
]
,(*Else if the integer set contains only whole numbers,*)
If[(sortedList[[1]]==0)&&(sortedList[[Length[sortedList]]]>0),
(*If the list of integers are all positive and m is negative,
there is no reason to proceed.*)
If[m<0,execute=False,(*Otherwise,*)
numberLine=
Join[
0(*zero*)
,
Range[sortedList[[Length[sortedList]]]](*positive integers*)
]
]
,(*Else if the integer set contains only the natural numbers.*)
(*If the list of integers are all positive and m is negative or zero,
there is no reason to proceed.*)
If[m<=0,execute=False,numberLine=Range[Max[sortedList](*positive integers*)]]
]
]
];
(*:::::Construction of numberline ENDS::::*)
(*Print[numberLine];*)
If[execute==False,finalList=$Failed,
(*Mark all numbers which are in numberline but are not in listOfIntegers with a period.
Sort[] will still sort this list of mixed precision of numbers in ascending order.*)
temp=Sort[Join[Complement[numberLine,sortedList]//N,sortedList]];
(*The main idea of the algorithm is to find the point on numberline to begin selecting two number
combinations which sum to m. m is obviously going to be used when that time comes.
Once that point is selected, integers symmetrically equally distant apart from each other
on both sides of this point (number) in numberline are candidates which sum to m.
To avoid going "out of bounds" of numberline (from either attempting to select a value smaller
than the minimum value of numberline or attempting to select a larger value than the maximum
value of numberline, the following is the maximum distance we can use to obtain ALL possible
two integer combinations which sum to m but of which also prevents us from going "out of bounds".)
*)
(*If the numberline we are about to create had a consistent minimum value of 1
then it would not be offset as it is in general.
The following takes this "offset" into account.*)
distanceFrom1ToMin=Abs[1-Min[sortedList]];
distance=
Min[
distanceFrom1ToMin+Floor[negativeFactor*m/2]
,
Length[temp]-(distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1)
];
start=distanceFrom1ToMin+Floor[negativeFactor*m/2]+1;
finish=distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1;
(*With the bound distance established, we are ready to begin selecting numbers from numberline.*)
finalList=;
i=1;
While[i<=distance,
finalList=Append[finalList,temp[[start-i]],temp[[finish+i]]];
i++
];
(*It turns out that for even m the first selected integer combination considered is m/2,m/2.*)
If[(Mod[m,2]==0)&&(MemberQ[finalList,negativeFactor*m/2,negativeFactor*m/2]==True),
(*Should there not be two of m/2 in listOfIntegers, we omit this selected combination.*)
If[Length[Flatten[Position[listOfIntegers,negativeFactor*m/2]]]<2,
finalList=Delete[finalList,Position[finalList,negativeFactor*m/2,negativeFactor*m/2][[1]][[1]]]
]
];
(*We selected all possible number combinations in numberline. However, unless listOfIntegers
is all consecutive integers, we need to omit any selected number combination in which either
of the numbers has a "." to the right of it.*)
finalList=negativeFactor*Sort[Select[finalList,Precision[#]==[Infinity]&]]
];
finalList
]
I did the following tests with the code and got these results. (The first number in the time in second it took to do the computation. But you can of course copy the code and do tests yourself.) I omitted most of the results from the last test because it made my post too large, but you will see that it did the computation in 0.209207 seconds.
As the comments in my algorithm (and the algorithm itself suggests), I broke up the number line into negative integers, zero, and the positive integers. I therefore wrote my tests to address all possible situations.
For the positive (non-zero) integer set.
With positive m such that m is larger than what any two number combination in listOfIntegers could possibly sum to.
m = 100; listOfIntegers = RandomSample[Range[20], 6]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
19, 11, 1, 4, 13, 17
0.0371008,
With positive odd m.
m = 215; listOfIntegers = RandomSample[Range[266], 190]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
119, 175, 7, 123, 42, 173, 15, 56, 233, 41, 9, 156, 130, 196, 183,
65, 102, 109, 177, 161, 230, 105, 91, 103, 146, 47, 234, 133, 88, 68,
169, 197, 46, 198, 108, 263, 205, 129, 4, 157, 245, 210, 203, 78,
172, 128, 138, 61, 262, 159, 148, 45, 225, 239, 72, 74, 151, 34, 36,
5, 106, 77, 223, 116, 8, 2, 11, 54, 124, 87, 221, 213, 171, 93, 53,
19, 40, 30, 95, 215, 39, 140, 49, 158, 94, 38, 28, 247, 84, 75, 257,
33, 163, 132, 69, 211, 193, 222, 114, 240, 32, 149, 167, 135, 107,
115, 101, 100, 166, 144, 251, 253, 224, 154, 48, 44, 26, 181, 259,
81, 6, 70, 122, 255, 189, 235, 112, 110, 174, 85, 147, 117, 18, 209,
66, 121, 155, 206, 207, 212, 98, 113, 254, 214, 178, 111, 227, 165,
204, 231, 194, 20, 176, 150, 162, 241, 243, 199, 90, 55, 127, 191,
12, 185, 242, 125, 265, 25, 1, 250, 201, 168, 76, 134, 266, 82, 10,
92, 143, 217, 126, 218, 182, 220, 153, 164, 216, 238, 67, 14
0.136695, 1, 214, 2, 213, 4, 211, 5, 210, 6, 209, 8,
207, 9, 206, 10, 205, 11, 204, 12, 203, 14, 201, 18,
197, 19, 196, 26, 189, 30, 185, 32, 183, 33, 182, 34,
181, 38, 177, 39, 176, 40, 175, 41, 174, 42, 173, 44,
171, 46, 169, 47, 168, 48, 167, 49, 166, 53, 162, 54,
161, 56, 159, 61, 154, 65, 150, 66, 149, 67, 148, 68,
147, 69, 146, 72, 143, 75, 140, 77, 138, 81, 134, 82,
133, 85, 130, 87, 128, 88, 127, 90, 125, 91, 124, 92,
123, 93, 122, 94, 121, 98, 117, 100, 115, 101,
114, 102, 113, 103, 112, 105, 110, 106, 109, 107, 108
With positive even m.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.00998522, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With positive even m such that listOfIntegers contains two of m/2.
m = 22; listOfIntegers = Append[Range[20], 11]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 11
0.00037181, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12, 11, 11
With positive even m such that listOfIntegers contains one m/2.
m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
0.000267311, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7,
15, 8, 14, 9, 13, 10, 12
With any negative m.
m = -6; listOfIntegers = Range[26]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26
0.000108231, $Failed
For the positive integer set (including 0).
With an even m.
m = 88; listOfIntegers = RandomSample[Join[0, Range[122]], 39]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
121, 69, 120, 56, 36, 55, 17, 114, 7, 59, 32, 4, 20, 79, 92, 62, 50,
89, 13, 70, 113, 75, 76, 80, 108, 53, 83, 95, 0, 85, 86, 77, 10, 54,
48, 66, 104, 100, 35
0.000505232, 13, 75, 32, 56, 35, 53
With an odd m.
m = 57; listOfIntegers = RandomSample[Join[0, Range[82]], 52]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
62, 18, 26, 0, 67, 34, 55, 52, 35, 78, 10, 68, 46, 44, 38, 23, 77,
76, 58, 51, 75, 63, 53, 42, 54, 27, 56, 71, 12, 17, 2, 37, 31, 72,
49, 50, 32, 16, 47, 19, 4, 20, 81, 25, 61, 14, 80, 82, 59, 33, 70, 39
0.000372743, 2, 55, 4, 53, 10, 47, 18, 39, 19, 38, 20,
37, 23, 34, 25, 32, 26, 31
For the negative integer set (including 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-2, -16, -15, -9, -5, -12, -8, -22, -7, -21, -13, -18, -4, -11, -10,
-19, -6, -17, -20
0.000105898, $Failed
With a negative odd m.
m = -17; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-5, -1, -10, -13, -15, -19, -2, 0, -7, -18, -3, -21, -8, -11, -12,
-22, -17, -16, -20
0.000640987, 0, -17, -1, -16, -2, -15, -5, -12, -7, -10
With a negative even m.
m = -26; listOfIntegers =
RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -16, -11, -14, -17, -13, -1, -9, -15, -20, -18, -4, -21, 0, -8,
-6, -10, -7, -3
0.000329357, -6, -20, -7, -19, -8, -18, -9, -17, -10,
-16, -11, -15
For the negative integer set (excluding 0).
With a positive m.
m = 4; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-20, -7, -16, -21, -11, -13, -5, -2, -6, -19, -1, -12, -18, -14,
-15, -9, -4, -17, -22
0.000102633, $Failed
With a negative odd m.
m = -27; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-18, -17, -22, -13, -1, -11, -19, -8, -16, -6, -21, -12, -20, -3,
-4, -9, -7, -14, -15
0.000242586, -6, -21, -7, -20, -8, -19, -9, -18, -11,
-16, -12, -15, -13, -14
With a negative even m.
m = -26; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-19, -10, -20, -9, -21, -14, -5, -1, -17, -4, -18, -22, -8, -6, -13,
-3, -2, -12, -15
0.000286438, -4, -22, -5, -21, -6, -20, -8, -18, -9, -17,
-12, -14
For the complete integer set.
With a positive odd m.
m = 15; listOfIntegers =
RandomSample[Join[-Range[52, 1, -1], 0, Range[52]], 35]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-30, 19, 42, 38, -25, 6, 48, 5, -8, -27, -11, -47, -37, -12, -3,
-34, 50, 11, 10, 18, 7, -15, 51, -22, -26, -2, 33, -35, 34, 39, 44,
-51, -33, -16, -23
0.000468378, -35, 50, -33, 48, -27, 42, -23, 38, -3,
18, 5, 10
With a negative odd m.
m = -7; listOfIntegers =
RandomSample[Join[-Range[22, 1, -1], 0, Range[22]], 21]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-1, -16, -11, 10, 17, 1, 0, -5, -22, 8, -7, 15, 21, 11, 18, 14, -4,
7, -13, 4, -9
0.000310697, -22, 15, -11, 4, -7, 0
With a positive even m.
m = 36; listOfIntegers =
RandomSample[Join[-Range[30, 1, -1], 0, Range[30]], 20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
25, -9, -8, 8, 5, -10, -24, 13, 9, -16, -23, -14, -22, -29, 26, 12,
19, 16, -30, 18
0.000289237,
With a negative even m.
m = -34; listOfIntegers =
RandomSample[Join[-Range[100, 1, -1], 0, Range[100]], 50]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
7, 92, 91, 58, -58, 63, -95, 82, 26, 60, 16, 65, 15, 34, 29, 67, -2,
88, 21, -72, -93, 12, 43, 18, -83, -80, -30, -6, 54, -13, -63, 39,
-55, 9, -78, 5, -16, 52, -24, -82, -18, 2, -90, 37, -60, 80, 57, -22,
-26, 72
0.000726359, -63, 29, -60, 26, -55, 21, -18, -16
With m == 0.
m = 0; listOfIntegers =
RandomSample[Join[-Range[222, 1, -1], 0, Range[222]], 111]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]
-215, -8, 186, 153, 17, 83, 149, -45, -18, 14, -161, 6, 84, -41,
-59, -130, 34, -24, -142, -95, -70, -60, -152, 90, -43, 12, -196,
-98, -193, -78, -192, 7, -30, 218, -209, -28, -125, 142, 11, 161,
-143, -135, -212, 134, 1, -177, -100, 2, 63, -180, -50, 79, -129,
-91, 126, 57, -140, -200, 38, -182, -107, -25, -46, -179, -113, 88,
148, 28, 184, -158, 190, -9, -36, -5, 169, 221, -204, -210, 44, 45,
-71, 40, 135, 119, -42, 166, 65, 59, -15, -118, 117, -47, -52, 102,
74, -19, 152, 81, 0, 170, -214, 114, -38, 210, -1, -7, -89, -173,
123, 78, -127
0.00179934, -210, 210, -161, 161, -152, 152, -142,
142, -135, 135, -78, 78, -59, 59, -45, 45, -38,
38, -28, 28, -7, 7, -1, 1
With a large m with a large listOfIntegers.
m = 5311; listOfIntegers =
RandomSample[Join[-Range[9999, 1, -1], 0, Range[9999]], 8888];
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
0.209207, -4680, 9991, -4676, 9987, -4664, 9975, -4650,
9961, -4646, 9957, -4645, 9956, -4636, 9947, -4634,
9945, -4633, 9944, -4630, 9941, -4600, 9911, -4599,
9910, -4594, 9905, -4587, 9898, -4574, 9885, -4573,
9884, -4572, 9883, -4566, 9877, -4562, 9873, -4556,
9867, -4549, 9860, -4538, 9849, -4529, 9840, -4517,
9828, -4514, 9825, -4511, 9822, -4504, 9815, -4502,
9813, -4499, 9810, -4497, 9808, -4490, 9801, -4486,
9797, -4485, 9796, -4483, 9794, -4481, 9792, -4478,
9789, -4475, 9786, -4464, 9775, -4463, 9774, -4458,
9769, -4452, 9763, -4443, 9754, -4431, 9742, -4428,
9739, -4427, 9738, -4420, 9731, -4417, 9728, -4407,
9718, -4405, 9716, -4397, 9708, -4394, 9705, -4393,
9704, -4380, 9691, -4377, 9688, -4369, 9680, -4359,
9670, -4356, 9667, -4354, 9665, -4350, 9661, -4349,
9660, -4346, 9657, -4337, 9648, -4332, 9643, -4331,
9642, -4325, 9636, -4323, 9634, -4314, 9625, -4305,
9616, -4293, 9604, -4283, 9594, -4266, 9577, -4246,
9557, -4241, 9552, -4235, 9546, -4231, 9542, -4227,
9538, -4224, 9535, -4222, 9533, -4220, 9531, -4211,
9522, -4203, 9514, -4202, 9513, -4198, 9509, -4196,
9507, -4193, 9504, -4190, 9501, -4181, 9492, -4176,
9487, -4148, 9459, -4138, 9449, -4137, 9448, -4136,
9447, -4127, 9438, -4125, 9436, -4107, 9418, -4086,
9397, -4081, 9392, -4079, 9390, -4078, 9389, -4065,
9376, -4056, 9367, -4041, 9352, -4040, 9351, -4038,
9349, -4035, 9346, -4030, 9341, -4026, 9337, -4020,
9331, -4015, 9326, -4014, 9325, -4010, 9321, -3991,
9302, -3988, 9299, -3984, 9295, -3980, 9291, -3978,
9289, -3977, 9288, -3976, 9287, -3971, 9282, -3970,
9281, -3950, 9261, -3946, 9257, -3938, 9249, -3932,
9243, -3922, 9233, -3920, 9231, -3915, 9226, -3910,
9221, -3909, 9220, -3908, 9219, -3901, 9212, -3900,
9211, -3898, 9209, -3887, 9198, -3885, 9196, -3877,
9188, -3875, 9186, -3869, 9180, -3864, 9175, -3859,
9170, -3854, 9165, -3853, 9164, -3848, 9159, -3839,
9150, -3835, 9146, -3826, 9137, -3821, 9132, -3812,
9123, -3810, 9121, -3807, 9118, -3806, 9117, -3799,
9110, -3797, 9108, -3789, 9100, -3779, 9090, -3777,
9088, -3774, 9085, -3773, 9084, -3769, 9080, -3767,
9078, -3761, 9072, -3751, 9062, -3750, 9061, -3749,
9060, -3748, 9059, -3742, 9053, -3740, 9051, -3731,
9042, -3726, 9037, -3717, 9028, -3715, 9026, -3714,
9025, -3708, 9019, -3704, 9015, -3702, 9013, -3687,
8998, -3677, 8988, -3661, 8972, -3654, 8965, -3653,
8964, -3649, 8960, -3641, 8952, -3635, 8946, -3622,
8933, -3615, 8926, -3610, 8921, -3607, 8918, -3601,
8912, -3597, 8908, -3592, 8903, -3586, 8897, ... , 2594, 2717, 2598, 2713, 2599, 2712, 2603,
2708, 2607, 2704, 2617, 2694, 2619, 2692, 2633,
2678, 2634, 2677, 2643, 2668, 2644, 2667, 2648,
2663, 2650, 2661
algorithm code-review
algorithm code-review
edited 4 hours ago
Henrik Schumacher
57.7k579158
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
Henrik Schumacher
57.7k579158
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
Henrik Schumacher
57.7k579158
edited 4 hours ago
Henrik Schumacher
57.7k579158
edited 4 hours ago
Henrik Schumacher
57.7k579158
57.7k579158
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
asked 4 hours ago
Christopher MowlaChristopher Mowla
1135
1135
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
The presence of anAppendindicates that the complexity of the algorithm is larger than you expect...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
You have aSortcall. UseSortByinstead, it is much faster thanSort. But you probably don't need to sort it anyway.
$endgroup$
– MikeY
3 hours ago
$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
32 mins ago
add a comment |
$begingroup$
The presence of anAppendindicates that the complexity of the algorithm is larger than you expect...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
You have aSortcall. UseSortByinstead, it is much faster thanSort. But you probably don't need to sort it anyway.
$endgroup$
– MikeY
3 hours ago
$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
32 mins ago
$begingroup$
The presence of an
Append indicates that the complexity of the algorithm is larger than you expect...$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
The presence of an
Append indicates that the complexity of the algorithm is larger than you expect...$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
You have a
Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.$endgroup$
– MikeY
3 hours ago
$begingroup$
You have a
Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.$endgroup$
– MikeY
3 hours ago
$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
32 mins ago
$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
32 mins ago
add a comment |
1 Answer
1
active
oldest
votes
11
$begingroup$
I think
IntegerPartitions[m, 2, listOfIntegers]
does exactly what you want, and seems pretty efficient.
answered 4 hours ago
RomanRoman
3,595820
$endgroup$
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f193945%2fthe-most-efficient-algorithm-to-find-all-possible-integer-pairs-which-sum-to-a-g%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
11
$begingroup$
I think
IntegerPartitions[m, 2, listOfIntegers]
does exactly what you want, and seems pretty efficient.
answered 4 hours ago
RomanRoman
3,595820
$endgroup$
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
add a comment |
11
$begingroup$
I think
IntegerPartitions[m, 2, listOfIntegers]
does exactly what you want, and seems pretty efficient.
answered 4 hours ago
RomanRoman
3,595820
$endgroup$
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
add a comment |
11
11
11
$begingroup$
I think
IntegerPartitions[m, 2, listOfIntegers]
does exactly what you want, and seems pretty efficient.
answered 4 hours ago
RomanRoman
3,595820
$endgroup$
I think
IntegerPartitions[m, 2, listOfIntegers]
does exactly what you want, and seems pretty efficient.
answered 4 hours ago
RomanRoman
3,595820
answered 4 hours ago
RomanRoman
3,595820
answered 4 hours ago
RomanRoman
3,595820
answered 4 hours ago
RomanRoman
3,595820
3,595820
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
add a comment |
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
$begingroup$
Thanks! I have used IntegerPartitions[] for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
38 mins ago
add a comment |
Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.
Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.
Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematica Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f193945%2fthe-most-efficient-algorithm-to-find-all-possible-integer-pairs-which-sum-to-a-g%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The presence of an
Appendindicates that the complexity of the algorithm is larger than you expect...$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
You have a
Sortcall. UseSortByinstead, it is much faster thanSort. But you probably don't need to sort it anyway.$endgroup$
– MikeY
3 hours ago
$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
32 mins ago