# Optimise CPU-intensive list combining function

I have a list of numbers list1 from which I want to create another list (list2) consisting of only those numbers that are equal to the sum of any two members of list1, as long as the total is under 15.

So for example if list1 = {1,4,6,8}, then I want list2 = {2,5,7,8,9,10,12,14}.

I could do this by:

list2 = Union[Flatten[Table[Table[i + j, {i, list1}], {j, list1}]]]

which does give the right result, but then I run into two problems:

1. I have no idea how to filter the list so that it only displays numbers less than 15. I tried appending /; x_ < 15 to the end, but this didn't do anything
2. This works fine for a list this small, but what I really want to do is scale this up to a list consisting of several thousand elements - for which it takes a very long time, and crashes my computer in the process. How could I make this function more efficient?

Thank you

-
Hmm... looks like there'll be a combinatorial explosion (even more so since you allow repetition). Why do you want to do this? Perhaps there's a better way to get to the result than brute-forcing... – R. M. Mar 5 '14 at 2:37
– R. M. Mar 5 '14 at 2:39
Deleted my answer, pending possible duplicate status, and clarification of what and why you're doing this: as rm-rf says, there may well be a much smarter way to do this. – ciao Mar 5 '14 at 3:02

## 1 Answer

Here's a way that avoids storing all the tuples. Save whether a sum has been found in an array (0 if no,1 if yes).

SeedRandom[1];
total = 100000;
list1 = Sort@RandomInteger[{1, total}, 1000];
results = ConstantArray[0, total];

Scan[Function[x, results[[Select[x + list1, # <= total &]]] = 1],
list1] // AbsoluteTiming
(*
{0.614213, Null}
*)

Pick[Range@total, results, 1] // Length
(*
80070
*)


For speed, a compiled position-finder. (TakeWhile was not fast.)

pos = Compile[{{list, _Integer, 1}, {limit, _Integer}},
Module[{last = Length@list},
Do[If[list[[i]] > limit, Return[last = i - 1]], {i,
Length@list}];
Return[last]
],
RuntimeOptions -> "Speed"];

Scan[Function[x,
results[[x + Take[list1, pos[list1, total - x]]]] = 1],
list1] // AbsoluteTiming
(*
{0.035715, Null}
*)

Pick[Range@total, results, 1] // Length
(*
80070
*)

-
Nice use of Part. Smart. +1 – ciao Mar 5 '14 at 3:18