2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – rm -rf
    Commented Mar 5, 2014 at 2:37
  • $\begingroup$ Duplicate: Memory efficient generation and selection of tuples $\endgroup$
    – rm -rf
    Commented Mar 5, 2014 at 2:39
  • $\begingroup$ 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. $\endgroup$
    – ciao
    Commented Mar 5, 2014 at 3:02

1 Answer 1

3
$\begingroup$

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
*)
$\endgroup$
1
  • $\begingroup$ Nice use of Part. Smart. +1 $\endgroup$
    – ciao
    Commented Mar 5, 2014 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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