Message Boards

WOLFRAM COMMUNITY

4388 Views

2 Replies

2 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Wolfram Language

Is there a fast way to find all multiple pairs in a list?

Paul Cleary

Posted 3 years ago

On small lists of numbers using subsets and cases works reasonably well, but is slow when the list contains a few million entries. list = {616, 720, 1352, 1504, 2288, 3136, 3744, 4600, 4752, 5720, 7000, 7280, 8568, 8800, 10296, 12312, 13832, 16456, 20224, 23400, 27056, 27720, 32032, 37904, 39208, 46376, 61272, 70720, 83600, 102200, 117936, 139392, 184016, 306720, 353912, 418264, 511216, 920200, 1533672, 4601024}; Cases[Subsets[list, {2}], {a_, b_} /; Mod[b, a] == 0] {{616, 27720}, {616, 32032}, {616, 418264}, {720, 306720}, {1352, 39208}, {2288, 32032}, {8568, 1533672}}

On small lists of numbers using subsets and cases works reasonably well, but is slow when the list contains a few million entries.

list = {616, 720, 1352, 1504, 2288, 3136, 3744, 4600, 4752, 5720, 
   7000, 7280, 8568, 8800, 10296, 12312, 13832, 16456, 20224, 23400, 
   27056, 27720, 32032, 37904, 39208, 46376, 61272, 70720, 83600, 
   102200, 117936, 139392, 184016, 306720, 353912, 418264, 511216, 
   920200, 1533672, 4601024};

Cases[Subsets[list, {2}], {a_, b_} /; Mod[b, a] == 0]

{{616, 27720}, {616, 32032}, {616, 418264}, {720, 306720}, {1352, 
  39208}, {2288, 32032}, {8568, 1533672}}

POSTED BY: Paul Cleary

2 Replies

Sort By:

Trevor Cappallo

Posted 3 years ago

I'm pretty sure it's the `Subsets` that really slows that down, I think that would try (and presumably fail) to create a list in memory of $10^{12}$ pairs, if you're using a set with a million numbers. Anyway, depends how fast you're looking for. My first stab is s = Sort[RandomInteger[{2, 100000000}, 100000]]; Timing[r = Flatten[Table[{s[[i]], #} & /@ Pick[s[[;; i - 1]], Mod[s[[i]], s[[;; i - 1]]], 0], {i, 2, Length@s}], 1]; r[[{1, 2, 3, -3, -2, -1}]]] which takes about 30 seconds on my machine for 100k numbers: `{30.1719, {{194616, 194616}, {348102, 498}, {355572, 498}, {99883982, 4540181}, {99889338, 498}, {99950842, 49975421}}}`

POSTED BY: Trevor Cappallo

Paul Cleary

Posted 3 years ago

Trevor, Thank you for your quick reply, your code is certainly faster without the subsets. here are a few results showing how much faster on the following length of list 1097 is x 39 3280 is x 78 9841 is x 2.68 29524 is x 2.66 There are some quite large numbers in the latter lists. The big difference is that last list used up almost 32gb memory using subsets and hardly anything with your code, so is a definite winner.

POSTED BY: Paul Cleary

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback