Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
    
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... –  rm -rf Mar 5 at 2:37
    
    
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. –  rasher Mar 5 at 3:02

1 Answer 1

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
*)
share|improve this answer
    
Nice use of Part. Smart. +1 –  rasher Mar 5 at 3:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.